【AtCoder Regular Contest 069 E】Frequency | Mrsrz's blog

贪心。

题目大意：

给定 $n$ 堆石子，要求依次进行以下操作直到无法操作：

1. 找到石头数量最多的一堆（如果相同则取最前面的那堆），将这堆的下标扔进队列。
2. 取走一堆中的一个石头。

可以发现这个队列的最终长度是一定的。

我们要求使得这个队列的字典序最小。求这个字典序最小的队列中，所有元素的出现次数。

题解：

显然取走石头数量最多的那个堆。

在出现相同的时候，我们先取后面的石头，这样可以保证字典序尽可能小。

其实这个方案等价于：把石头数量最多的堆的每堆都取到严格第二多的堆的数量（从后往前取）。

所以可以排序以后，写出一个贪心的算法。

每次记录当前石头数量、当前位置最小值、当前的数的个数即可。

Code：

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+6;
int n;
LL ans[N];
struct data{
    int u,d;
    inline bool operator<(const data&rhs)const{return d==rhs.d?u<rhs.u:d>rhs.d;}
}a[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int x;
        scanf("%d",&x);
        a[i]=(data){i,x};
    }
    sort(a+1,a+n+1);
    int id=a[1].u,cnt=a[1].d;
    for(int i=2;i<=n+1;++i)if(cnt>a[i].d){
        ans[id]+=(cnt-a[i].d)*(i-1LL);
        cnt=a[i].d;
        id=min(id,a[i].u);
    }
    for(int i=1;i<=n;++i)printf("%lld\n",ans[i]);
    return 0;
}