Codeforces Round #629 (Div. 3) F. Make k Equal 思维

ゝ一纸荒年。 2023-05-28 05:15 26阅读 0赞

题目链接：https://codeforces.com/contest/1328/problem/F  
题意：给你n个数字的序列，每次你可以将最大的数减一，最小的数加一，问最少多少次操作后有k个相等的数  
思路：例如对于a\[i\], 我们需要将前面的改成a\[i\] - 1, 将后面的改成a\[i\] + 1, 所以我们将数组排序后  
用map分别记录一下某个值第一次出现和最后一次出现的位置，然后On 遍历对于每个值计算只考虑前面的花费  
和只考虑后面的花费或者前后同时都考虑的花费，取最优

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define fi first
    #define se second
    #define ls rt << 1
    #define rs rt << 1|1
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    #define pll pair<ll, ll>
    #define pii pair<int, int>
    #define ull unsigned long long
    #define pdd pair<double, double>
    const int mod = 1e9 + 7;
    const int maxn = 2e5 + 10;
    const int inf = 0x3f3f3f3f;
    map<int, int> L, R;
    int a[maxn];
    ll sum[maxn];
    
    int main()
    {
        int n, k;
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        for(int i = 1; i <= n; ++i)
        {
            if(!L.count(a[i]))
                L[a[i]] = i;
            sum[i] = sum[i - 1] + a[i];
        }
        for(int i = n; i >= 1; --i)
        {
            if(!R.count(a[i]))
                R[a[i]] = i;
        }
        ll ans = 0x3f3f3f3f3f3f3f3f;
        for(int i = 1; i <= n; ++i)
        {
            int num = k - (R[a[i]] - L[a[i]] + 1);
            if(num <= 0)
            {
                ans = 0;
                break;
            }
            ll res1 = 1ll * (a[i] - 1) * (L[a[i]] - 1) - sum[L[a[i]] - 1];
            ll res2 = sum[n] - sum[R[a[i]]] - 1ll * (a[i] + 1) * (n - R[a[i]]);
            if(i >= k) ans = min(ans, res1 + num);
            if(i <= n - k + 1) ans = min(ans, res2 + num);
            ans = min(ans, res1 + res2 + num);
        }
        printf("%lld\n", ans);
        return 0;
    }