Codeforces Round #629 (Div. 3) F. Make k Equal 思维
题目链接: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;
}
还没有评论,来说两句吧...