A. Iskander and Drawings

Problem: A. Iskander and Drawings

Contest: Codeforces - Codeforces Round 1109 (Div. 3)

URL: https://codeforces.com/contest/2244/problem/A

Memory Limit: 256 MB

Time Limit: 1000 ms

Powered by CP Editor (https://cpeditor.org)

解题思路

原本以为是模拟，但是后面发现，本题实际上是贪心，两人从两边分开擦除，每次擦除1个单位，所以最大时间就是每段线的长度的一半，因为1-2时，直接擦除即可。所以总时间是每段线的长度的一半向上取整。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	while(n--){
		int m;
		cin>>m;
		string s;
		cin>>s;
		int res=0,t=0;
		for(auto i:s){
			if(i=='#')t++;
			else t=0;
			res=max(res,(t+1)/2);
		}
		cout<<res<<'\n';
	}
	return 0;
}

B. Nikita and Books

Problem: B. Nikita and Books

Contest: Codeforces - Codeforces Round 1109 (Div. 3)

URL: https://codeforces.com/contest/2244/problem/B

Memory Limit: 256 MB

Time Limit: 1000 ms

Powered by CP Editor (https://cpeditor.org)

解题思路

从题目中看，书籍最终要满足严格递增，且只能向右移动，最小的严格递增整数序列为1,2,3~n，所以如果序列要保证最终可以满足严格递增序列，那么前i项的和必须要大于或等于最小的严格递增序列和，否则无法满足条件。 则我们只需遍历数组求和，判断前i项和是否满足大于等于最小的严格递增序列和，即$sum_i \geq \frac{i(i+1)}{2}$

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		ll sum=0,temp=0;
		int flag=0;
		for(ll i=1;i<=n;i++){
			cin>>temp;
			sum+=temp;
			if(sum<(i*(i+1)/2)){
				flag=1;
			}
		}
		if(flag)cout<<"NO"<<'\n';
		else cout<<"YES"<<'\n';
	}
	
	return 0;
}