Codeforces Round 973 (Div. 2)

A - Zhan's Blender

由于总量固定 因此只用计算两个处理时间 最大值即是所求

#include<bits/stdc++.h>
using namespace std;
int n;
double x, y;
 
void solve(){
	cin >> n;
	cin >> x >> y;
	int tim1 = ceil(n * 1.0 / x);
	int tim2 = ceil(n * 1.0 / y);
	cout<< max(tim1, tim2) << endl;
	
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int _;
	cin >> _;
	while(_--){
		solve();	
	}
	return 0;
} 

B - Battle for Survive

因为每次操作都是后一个减去前一个，因此末尾数字总是存在

所以我们只需要维持倒数第二个数字最小，

所以我们让前n - 2个数字去和n - 1数字进行操作

得到最小的n - 1数字，最后用n - 1和n进行最后一次操作就能得到答案

#include<bits/stdc++.h>
using namespace std;
int n;
long long num;
vector<int> fit(200000, 0);
void solve(){
	cin >> n;
	num = 0;
	for(int i = 0; i < n; ++i){
		cin >> fit[i];
	}
	if(n == 2){
		cout << fit[1] - fit[0] << endl;
		return;
	}else{
		for(int i = 0; i < n - 2; ++i){
			num += fit[i];
		}
		cout << fit[n - 1] - (fit[n - 2] - num) << endl;
		return;
	}
}
 
int main(){
	int _;
	cin >> _;
	while(_--){
		solve();	
	}
	return 0;
} 

D - Minimize the Difference

因为若a_i > a_i + 1,那么我们进行转移，因为从前向后转移即便对当前无益，但后面可能有元素需要进行添加，而当前操作不会对整个队列产生负面影响，因此，我们总是进行转移。

建立一个栈，每次都从外部取新的元素b放进来，然后从队列尾部取出元素a开始判断，如果a大于等于b。

将a取出，乘上a的个数，于b乘b的个数加到一起，计算平均数。

将b更新为这个新的平均数，数量也进行更新，继续从队列中取出元素，重复上述操作

最后，用得到的总和和元素数量计算出新的数，放入栈中。

用栈中的头元素，减去尾元素，就能得到答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200200];
int n;

void solve(){
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];//读入原始数组 
	}
	stack<pair<ll, int>> s;
	for(int i = 1; i <= n; ++i){
		ll sum = a[i], cnt = 1;//取出一个新元素，将其添加到栈中 
		//如果栈不为空，并且栈顶的元素的值大于均值(用取出的所有数的和/位置) 
		while(s.size() && s.top().first >= sum / cnt){
			sum += s.top().first * s.top().second;//将其取出 
			cnt += s.top().second;
			s.pop();
		}
		//将新的数和位置放入栈中
		s.push({sum / cnt, cnt - sum % cnt}); 
		if(sum % cnt != 0){
			s.push({sum / cnt + 1, sum % cnt});
		}
	}//头元素和尾元素 相减求出答案 
	ll mx = s.top().first;
	while(s.size() > 1){
		s.pop();
	}
	cout << mx - s.top().first << '\n';
}
int main(){
	int _;
	cin >> _;
	while(_--){
		solve();
	}
	return 0;
} 

E - Prefix GCD

1、先求出所有元素的gcd--g并将所有元素都除以g

2、对剩下的所有数据进行暴力查找，如果出现1， 剩余的全为1

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

int n, k;
int a[200200];

void solve(){
	cin >> n;
	int g = 0, cur = 0;
	long long ans = 0;
	for(int i = 0; i < n; ++i){//求全体共同的最大公因数 
		cin >> a[i];
		g = __gcd(g, a[i]);
	}
	for(int i = 0; i < n; ++i){
		a[i] /= g;
	}
	//循环已经找到元素的个数 
	for(int t = 0; t < n; ++t){
		int nc = 1e9;
		for(int i = 0; i < n; ++i){//查找剩下的元素， 
			nc = min(nc, __gcd(cur, a[i]));
		}
		cur = nc;//下一轮找比cur更小的 
		ans += cur;//将最小的加进去 
		if(cur == 1){//如果为1，剩下的就不用判断了 
			ans += n - t - 1;
			break;
		}
	}
	//输出答案乘g 
	cout << ans * g << "\n";
}

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

数组的 GCD 在最多 10 次迭代后最终会达到 1。

为什么是 10 次迭代？：从数论来看，数字序列的 GCD 是一个非递增函数。这意味着 GCD 要么保持不变，要么随着添加到数组中的每个新元素而减少。在实践中，已经观察到 GCD 可以在非常少的迭代次数（最多 10 次）内减少到 1。这是因为一旦 GCD 开始变小，可以添加的数字集就会变得更加有限，并且达到 GCD 1 所需的步骤更少。

                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         I have a dream! An AC dream!!