题解：CF2254D Silhouette

fish_love_cat · 2026-08-10 03:10:27 · 题解

显然影子相同的元素相等。

按照影子从小向大考虑，相同合并，不同做个差分可以得到前面这一车相同元素产生的贡献。

贡献和有了，统计一下元素数量，可以算出每个点的大小，注意要检查单调性。

最小化字典序，我们在这个基础上直接最小化所有元素的取值就可以了，显然是不会劣的。

注意最后要以原顺序输出。

因为排序所以 O(n\log n)。

int ans[200005];
int an2s[200005];
struct fish{
    int x,id;
}a[200005];
bool cmp(fish x,fish y){
    return x.x<y.x;
}
inline void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i].x,a[i].id=i,ans[i]=0;
    sort(a+1,a+1+n,cmp);
    int siz=0,qwq=0,pwp=1;
    int mx=0;
    for(int i=1;i<=n;i++){
        if(a[i].x==qwq)siz++;
        else{
            int flc=a[i].x-qwq;
            if(siz==0||flc%siz!=0){
                cout<<"-1\n";
                return;
            }
            pwp=flc/siz;
            qwq=a[i].x;
            for(int j=1;j<=siz;j++)
            ans[i-j]=pwp;
            mx=max(mx,pwp);
            siz=1;
        }
    }
    for(int i=1;i<=n;i++)
    if(ans[i]==0)ans[i]=mx+1;
    for(int i=2;i<=n;i++)
    if(ans[i]<ans[i-1]||ans[i]==ans[i-1]&&a[i].x!=a[i-1].x){
        cout<<"-1\n";
        return;
    }
    for(int i=1;i<=n;i++)
    an2s[a[i].id]=ans[i];
    for(int i=1;i<=n;i++)cout<<an2s[i]<<' ';
    cout<<'\n';
}
// 一路雾色太过朦胧
// 世界拆碎成千万种
// 掌心攥着谁的悸动
// 你我相拥还是惶恐

// 大雨下的浇醒了梦
// 只能奔跑追逐着风
// 不敢弄丢你的行踪
// 握紧的手怎会再松