CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!) C. Make It Permutation

r囧r小猫 2024-03-24 12:57 64阅读 0赞

[Problems - Codeforces][]

题意：

![8339051d6f2741b5ab9a8b0135eedfbb.png][]

![9c592e44e36b47d5a66894afdb5c7b26.png][]

思路：

题目只要求最后是个排列就行，和位置无关，因此可以考虑给它排个序

然后因为构造成什么排列是不确定的，因此我们去暴力枚举构造成的是1~x的排列

然后对于枚举的每种情况，都去O(1)地计算贡献，然后统计即可

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e5+10;
    const int mxe=5e4+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    set<int> S;
    int n,c,d;
    int a[mxn];
    void solve(){
        S.clear();
        cin>>n>>c>>d;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n);
        int ans=1e9;
        if(a[1]==1) ans=(n-1)*c;
        else ans=n*c+d;
        int res;
        for(int i=1;i<=n;i++){
            S.insert(a[i]);
            res=(n-S.size())*c+(a[i]-S.size())*d;
            ans=min(ans,res);
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problems - Codeforces]: https://codeforces.com/contest/1810/problems
[8339051d6f2741b5ab9a8b0135eedfbb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/1eab2e5e1278454ca5a5aa58e32c155d.png
[9c592e44e36b47d5a66894afdb5c7b26.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/98933f71592b4102a8787646ffba45ad.png