Codeforces Round 974 (Div. 3)

A - Robin Helps

按题目要求一步步计算就行

#include<bits/stdc++.h>
using namespace std;

int n, k;
void solve(){
	cin >> n >> k;
	int sum = 0, num, ans = 0;
	for(int i = 1; i <= n; ++i){
		cin >> num;
		if(num >= k){
			sum += num;//拿走所有
		}else if(num == 0){
			if(sum > 0){//如果有金币
				sum--;//减去一个现有金币
				ans++;//加一个被施舍的人
			}
		}
	}
	cout<< ans << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int _;
	cin >> _;
	while(_--){
		solve();	
	}
	return 0;
}

B - Robin Hood and the Major Oak

偶数乘偶数还是偶数，奇数乘奇数还是奇数

因为偶数无法对当前奇偶产生影响，因此直接对区间内奇数进行判断，

因为持续时间为k，那么n - k + 1之前的所有叶子都不会对结果产生任何影响

综上，找到有效区间，进行区间内奇数个数的统计，就能得到答案

#include<bits/stdc++.h>
using namespace std;

int n, k;
void solve(){
	cin >> n >> k;
	int year = 1;
	if(k >= n){
		if(n % 2 == 1){
			year = n / 2 + 1;
		}else{
			year = n / 2;
		}
	}else{
		if(k % 2 == 1){
			if(n % 2 == 1){
				year = k / 2 + 1;
			}else{
				year = k / 2;
			}
		}else{
			year = k / 2;
		}
	}
	
	if(year % 2 == 0){
			cout << "YES" << endl;
			return ;
		}
	cout << "NO" << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int _;
	cin >> _;
	while(_--){
		solve();	
	}
	return 0;
}

C - Robin Hood in Town

读入，对财富进行排序。特判n为1和2的时候

找出严格中值，对其乘2乘n，计算出不会让罗宾汉出现的最低财富总值minn

用minn和现有财富进行比较，输出结果（相等的时候结果为一，不等的时候向上取整）。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n;
long double peo[N], sum[N];
long double num;

void solve(){
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> peo[i];
		sum[i] = sum[i - 1] + peo[i];
	}
	
	if(n < 3){
		cout << "-1" << endl;
		return;
	}
	
	int mid = n / 2 + 1;
	sort(peo + 1, peo + 1 + n);
	long double minn = peo[mid] * n * 2.0;
	if(minn < sum[n]){
		cout << 0 << endl;
		return;
	}
	long long ans = (minn - sum[n]);
	ans++;
	cout << ans << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int _;
	cin >> _;
	while(_--){
		solve();	
	}
	return 0;
}

D - Robert Hood and Mrs Hood

#include<bits/stdc++.h>
using namespace std;

void work(){
	int n, k, d;
	cin >> n >> d >> k;
	vector<int>  ss(n + 1), es(n + 1);
	
	for(int i = 0; i < k; ++i){
		int a, b;
		cin >> a >> b;
		ss[a]++;//标记开始时间 
		es[b]++;//标记结束时间 
	}
	//计算 
	for(int i = 0; i < n; ++i) ss[i + 1] += ss[i];
	for(int i = 0; i < n; ++i) es[i + 1] += es[i];
	int most = 0;
	int robert = 0;
	int mrs = 0;
	int least = 1e9;
	for(int i = d; i <= n; ++i){
		int cur = ss[i] - es[i - d];//计算当前天数有几份工作 
		if(cur > most)most = cur, robert = i - d + 1;//更新最大值 
		if(cur < least)least = cur, mrs = i - d + 1;//更新最小值 
	}
	cout << robert << ' ' << mrs << '\n';//输出 
}

int main(){
	int t;
	cin >> t;
	while(t--) work();
	return 0;
}