题解：AT_arc069_c [ARC069E] Frequency

cvd420 · 2025-04-08 15:34:03 · 题解

注意到 S 序列单调递减，否则一定不优。

于是从大到小选择模拟

code:

//created by fqr & cyx in 2025
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ll long long
#define pb emplace_back
int ff,Ch;
template <typename T> inline void rd(T &x) {
    x=0,ff=1,Ch=getchar();
    while((Ch<'0'||Ch>'9') && Ch!='-') Ch=getchar();
    if(Ch=='-')Ch=getchar(),ff=-1;
    while(Ch>='0' && Ch<='9') {
        x=(x<<1)+(x<<3)+Ch-'0';
        Ch=getchar();
    }
    x*=ff;
}
template <typename T,typename ...Args> inline void rd(T &x,Args &...args) {
    rd(x), rd(args...);
}
using namespace std;
const int N=1e5+5;
int n; 
int a[N],p[N];
ll ans[N];
signed main() {
#ifdef LOCAL
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
#endif
    rd(n);
    for(int i=1; i<=n; i++)
        rd(a[i]),p[i]=i;
    sort(p+1,p+1+n,[&](const int &x,const int &y) {
        return a[x]>a[y];
    });
    ll sum=a[p[1]];
    for(int i=2,lst=1; i<=n+1; i++) {
        if(p[i]<p[lst]) {
            ans[p[lst]]=sum-1ll*(i-1)*a[p[i]];
            sum=(i-1)*a[p[i]];
            lst=i;
        }
        sum+=a[p[i]];
    }
    for(int i=1; i<=n; i++)
        printf("%lld\n",ans[i]);
    return 0;
}