因为显然操作次数越多，最大值越小，存在一个单调性
这时候得到一个操作完成后的最大值max，那么可以把数组进行操作，把所有数变为≤max的形式
此时，k-n＜操作次数≤k，所以最后至多只要再操作n-1次，当且仅当数组中所有数都max时还需操作次数n-1次
反证法证明，如果还要操作n次或n次以上，数组最大值必定＜max，与上矛盾，故最多再操作n-1次
因此，得到max并把数组进行初步更改后，还剩余一个操作次数k1(k-n＜k1≤k)，且被再次修正的数必定等于max
直接for一遍进行二次修改，最后sort输出即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1000005];
ll k,p;
int n;
bool check(ll x){
ll s=0;
for (int i=1;i<=n;i++)
if (a[i]>x){
ll t=(a[i]-x-1)/p+1;
s+=t;
if (s>k)return 0;
}
return 1;
}
int main(){
scanf("%d%lld%lld",&n,&k,&p);
for (int i=1;i<=n;i++)scanf("%lld",&a[i]);
if (p==0||k==0){
sort(a+1,a+1+n);
for (int i=1;i<=n;i++)printf(i==n?"%lld\n":"%lld ",a[i]);
return 0;
}
ll l,r,mid;
r=9223372036854775807;
ll ans=l=-r;
while (l<=r){
mid=(l+r)/2;
if (check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
ll s=0;
// printf("%lld\n",ans);
for (int i=1;i<=n;i++)
if (a[i]>ans){
s=(a[i]-ans-1)/p+1;
a[i]-=s*p;
k-=s;
}
for(int i=1;i<=n&&k;i++)
if(a[i]==ans)a[i]-=p,k--;
sort(a+1,a+1+n);
for (int i=1;i<=n;i++)printf("%lld ",a[i]);
} 
全部评论
(0) 回帖