题目链接。

题意不多赘述。

解析

由于每次会将石子最多的那堆的序号加入 $S$ 中，我们考虑将原始的石子堆从大到小排序。首先我们发现如果有一堆比其他都要高，我们可以将他取到与第二高的一样高，这样的话结果只可能会更优（因为相同时优先取小的）。

依照这个思路，我们考虑按照高度一层一层取下来，这样答案会越来越优（若存在多个高度相同的，你只需要认为在取的过程中先取序号大的即可）。由于高的不取完矮的一定无法加入 $S$，因此这样一定是最优结果。

也就是说，我们只需要记录从开始（从最高的开始）到当前所有堆中序号最小的那个，然后每次变层时，将当前最小的答案加上高度差乘以大于等于该层的所有堆数量的结果即可（相当于削掉这层以上的部分），详见代码。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,maxx,ans[N];
struct node{
    int p,a;
}a[N];
inline bool cmp(node i,node j){
    if(i.a!=j.a) return i.a>j.a;
    return i.p>j.p;//同层的直接让序号小的在后面，后续方便一些
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].a);
        a[i].p=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1,now=1e9+7;i<=n;i++){
        if(i!=n&&a[i].a==a[i+1].a) continue;//同层的跳过
        now=min(now,a[i].p);//更新当前最小值
        ans[now]+=i*(a[i].a-a[i+1].a);//加入削掉这层以上部分所需的次数
    }
    for(int i=1;i<=n;i++)
        printf("%lld\n",ans[i]);
    return 0;
}