首页 > 练习赛83-C集合操作
头像
213dd
发布于 2021-05-22 21:34
+ 关注

练习赛83-C集合操作

首先可以把操作完成后的最大值进行二分
因为显然操作次数越多,最大值越小,存在一个单调性
这时候得到一个操作完成后的最大值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) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐