自动搬运

查看原文

来自洛谷，原作者为

	Expert_Dream **

搬运于2025-08-24 22:53:32，当前版本为作者最后更新于2023-12-24 17:47:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

博客园。

首先我们知道，对于 $a_1$ 每一次是最先吃糖果的。所以必然有两个情况：

• 全部给他吃了。
• 吃了一些。

首先情况一，我们可以直接特判掉。

剩下情况二，吃了一些没吃完代表：吃了自己的高度，相当于身高 $\times 2$。于是我们只需要进行 $\log 10^9$ 次。然后后面直接 $O(n)$ 暴力。时间复杂度 $O(n \log 10^9)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
#define int long long
int n,m;
int a[N],b[N];
void solve(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	for(int i = 1;i <= m;i++)
		cin >> b[i];
	
	
	for(int i = 1;i <= m;i++){
		if(b[i] <= a[1]){
			a[1]+=b[i];
			continue;
		} 
		int tmp = 1;
		for(int j = 1;j <= n;j++)
			if(a[j] >= tmp && tmp <= b[i]){
				int t=a[j]+1;
				a[j] += min(a[j]-tmp+1,b[i]-tmp+1);
				tmp = t;
			}
	}
	
	for(int i = 1;i <= n;i++)
		cout<<a[i]<<endl;
	
}

signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}