P9974

Expert_Dream · 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;
}