AT_abc388_d 题解

ikunTLE · 2025-01-12 07:06:52 · 题解

题目传送门

思路

可以使用优先队列解决此题。

不难考虑到暴力思路：当遍历到 i 时，将前 i-1 个不为 0 的数都减 1，并将不为 0 的数字个数加在 A_i 上。

然后发现，假设 A_i 足够大，第 i 位要送出的石头个数为 A_i-N+i。然后考虑 A_i 不够大的情况，最终 A_i=0，并且它为后面数的贡献会减小。

考虑优先队列进行优化。每一次将贡献为 0 的外星人全部弹掉，剩下的外星人都能为当前位做贡献，A_i 直接加上容器的大小，然后再将 A_i 放入队列中。

最终答案有可能为 0，故输出 \max(0,A_i-N+i)。

由于使用了优先队列，时间复杂度为 \mathcal{O}(N\log N)。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=5e5+10;
int a[N];
struct node{
    int x,id;
    friend bool operator<(const node cmp_x,const node cmp_y){
        return cmp_x.x>cmp_y.x;
    }
};priority_queue<node>pq;
signed main(){
    int n=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    for(int i=1;i<=n;++i){
        a[i]+=pq.size();
        while(!pq.empty()&&pq.top().x-i<=0)
            pq.pop();
        if(a[i])
            pq.push({a[i]+i,i});
    }
    for(int i=1;i<=n;++i)
        printf("%lld ",max(0ll,a[i]-n+i));
    printf("\n");
    return 0;
}