codeforces-1328F-Make k Equal

传送门：https://codeforces.com/contest/1328/problem/F

题意：把n个数变成k个相同的数每次可以把n个数里最大的-1或最小的+1，问最小改变次数

我们可以枚举，把n个数变成k个a[i]（这个相同的数一定是数组里的数，因为如果不是，那么改变次数一定会比正常多）

如果相同的数大于k个，那么改变次数为0，特判掉

有三种情况，一种是只动前面，一种只动后面，还有就是前后都动

因为是改变最大或最小的数，所以我们只有把所有小于a[i]的数变成a[i]-1（或者大于a[i]的数变成a[i]+1）才能进行下一次的改变

然后接着考虑，在什么情况下可以动前面呢，当然是他前面的数大于（k-1）个，同理，在他后面的数大于（k-1）个时才可以动后面，然后在任何情况下都可以前后都动（（在i==1）时就相当于是动后面结果不冲突）

以只动前面为例

$tem1=(\sum_{j=1}^{i}((a[i]-1)-a[j]))+k$

化简一下发现

$tem1=\sum_{j=1}^{i}(a[i]-1)-\sum_{j=1}^{i}a[j]+k$

就是i*(a[i]-1)-a[i]的前缀和+k,提前搞一个前缀和可以降低时间复杂度

只动后面同理

$tem2=\sum_{j=i}^{n}a[j]-\sum_{j=i}^{n}(a[i]+1)+k$

动两边，这时相等的数的个数恰好为n，把他们都搞成a[i]然后再减掉多余的

$tem3=\left ( \sum_{j=i}^{n}a[j] \right )-\left ( \sum_{j=1}^{i}a[j] \right )+\left ( \sum_{j=1}^{i}a[i] \right )-\left( \sum_{j=i}^{n}a[i] \right )-(n-k)$

记录好前缀和和（后缀和？）就可以用o(n)的复杂度解决掉这个问题了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const ll inf=1e17;
 5 ll a[200009];
 6 ll cnt[200009];
 7 ll sumq[200009],sumh[200009];
 8 int main()
 9 {
10     int n,k;
11     ll ans=inf;
12     scanf("%d%d",&n,&k);
13     for(int i=1; i<=n; i++)
14     {
15         scanf("%lld",&a[i]);
16     }
17     sort(a+1,a+1+n);
18     for(int i=1; i<=n; i++) sumq[i]=sumq[i-1]+a[i];
19     for(int i=n; i>=1; i--) sumh[i]=sumh[i+1]+a[i];
20     for(int i=1; i<=n; i++)
21     {
22         if(a[i]==a[i-1])cnt[i]=cnt[i-1]+1;
23         else cnt[i]=1;
24         if(cnt[i]>=k)
25         {
26             puts("0");
27             return 0;
28         }
29     }
30     for(int i=1; i<=n; i++)
31     {
32         if(i>=k)
33         {
34             ll tem1=i*(a[i]-1)-sumq[i]+k;
35             ans=min(tem1,ans);
36         }
37         if(n-i+1>=k)
38         {
39             ll tem2=n-i+1;
40             tem2=sumh[i]-tem2*(a[i]+1)+k;
41             ans=min(tem2,ans);
42         }
43         if(i<k&&(n-i+1)<k)
44         {
45             ll tem3=i*a[i]-sumq[i]+sumh[i]-(n-i+1)*a[i]-(n-k);
46             ans=min(tem3,ans);
47         }
48     }
49     printf("%lld
",ans);
50     return 0;
51 }

$n$