首页王道数据结构课后5.4.4

王道数据结构课后5.4.4

时间: 2023-06-28 10:08:07 浏览: 119

题目描述：给定一个长度为n的数列，每次可以将一个数加上或减去k，最少需要几次操作才能使所有数相等。思路分析：首先，我们可以假设最终相等的数为x，那么对于一个数a[i]，需要进行的操作次数即为|a[i]-x|/k，向上取整（因为只能加减k，无法精确调整），所以问题转化为求最小的x，使得所有的|a[i]-x|/k之和最小。考虑贪心，如果存在两个数 a[i] 和 a[j]，它们的差大于等于2k，那么将它们都调整为它们的平均数，即 (a[i]+a[j])/2，这样可以使得|a[i]-x|/k和|a[j]-x|/k都会减少至少一次，同时可以保证调整后的差小于2k。对于差小于2k的数对，它们的调整是相互独立的，不会影响其他数对的调整。因此，我们可以先对数列进行排序，再枚举相邻的数对，如果它们的差大于等于2k，就将它们调整为它们的平均数，直至所有数对的差都小于2k。最后，计算所有数与平均数的差值之和，除以k并向上取整即为答案。参考代码： ```c++ #include<algorithm> #include<cstdio> #include<cmath> using namespace std; typedef long long ll; const int N=1e5+5; int n,k,a[N]; ll ans; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) scanf("%d",&a[i]); sort(a+1,a+n+1); int l=1,r=n; while(l<r) { int d=a[r]-a[l]; if(d>=2*k) { int x=(a[l]+a[r])/2; int cnt1=0,cnt2=0; for(int i=l;i<=r;++i) { cnt1+=(abs(a[i]-x)+k-1)/k; cnt2+=(abs(a[i]-x-k)+k-1)/k; } if(cnt2<cnt1) x-=k; for(int i=l;i<=r;++i) ans+=abs(a[i]-x); break; } else { int x=a[l]+k,y=a[r]-k; int cnt1=0,cnt2=0; for(int i=l;i<=r;++i) { cnt1+=(abs(a[i]-x)+k-1)/k; cnt2+=(abs(a[i]-y)+k-1)/k; } if(cnt1<cnt2) ans+=cnt1*k,l++; else ans+=cnt2*k,r--; } } printf("%lld\n",ans/k); return 0; } ```

阅读全文