【AtCoder Regular Contest 069 E】Frequency
贪心。
题目大意:
给定 $n$ 堆石子,要求依次进行以下操作直到无法操作:
- 找到石头数量最多的一堆(如果相同则取最前面的那堆),将这堆的下标扔进队列。
- 取走一堆中的一个石头。
可以发现这个队列的最终长度是一定的。
我们要求使得这个队列的字典序最小。求这个字典序最小的队列中,所有元素的出现次数。
题解:
显然取走石头数量最多的那个堆。
在出现相同的时候,我们先取后面的石头,这样可以保证字典序尽可能小。
其实这个方案等价于:把石头数量最多的堆的每堆都取到严格第二多的堆的数量(从后往前取)。
所以可以排序以后,写出一个贪心的算法。
每次记录当前石头数量、当前位置最小值、当前的数的个数即可。
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;
}