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

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

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

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define fi first
  5. #define se second
  6. #define ls rt << 1
  7. #define rs rt << 1|1
  8. #define lson l, mid, ls
  9. #define rson mid + 1, r, rs
  10. #define pll pair<ll, ll>
  11. #define pii pair<int, int>
  12. #define ull unsigned long long
  13. #define pdd pair<double, double>
  14. const int mod = 1e9 + 7;
  15. const int maxn = 2e5 + 10;
  16. const int inf = 0x3f3f3f3f;
  17. map<int, int> L, R;
  18. int a[maxn];
  19. ll sum[maxn];
  20. int main()
  21. {
  22. int n, k;
  23. scanf("%d%d", &n, &k);
  24. for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  25. sort(a + 1, a + n + 1);
  26. for(int i = 1; i <= n; ++i)
  27. {
  28. if(!L.count(a[i]))
  29. L[a[i]] = i;
  30. sum[i] = sum[i - 1] + a[i];
  31. }
  32. for(int i = n; i >= 1; --i)
  33. {
  34. if(!R.count(a[i]))
  35. R[a[i]] = i;
  36. }
  37. ll ans = 0x3f3f3f3f3f3f3f3f;
  38. for(int i = 1; i <= n; ++i)
  39. {
  40. int num = k - (R[a[i]] - L[a[i]] + 1);
  41. if(num <= 0)
  42. {
  43. ans = 0;
  44. break;
  45. }
  46. ll res1 = 1ll * (a[i] - 1) * (L[a[i]] - 1) - sum[L[a[i]] - 1];
  47. ll res2 = sum[n] - sum[R[a[i]]] - 1ll * (a[i] + 1) * (n - R[a[i]]);
  48. if(i >= k) ans = min(ans, res1 + num);
  49. if(i <= n - k + 1) ans = min(ans, res2 + num);
  50. ans = min(ans, res1 + res2 + num);
  51. }
  52. printf("%lld\n", ans);
  53. return 0;
  54. }

发表评论

表情:
评论列表 (有 0 条评论,15人围观)

还没有评论,来说两句吧...

相关阅读