二分#

一些奇奇怪怪的二分#

CF2120 有个显然的贪心是将最大的末尾移到最小末尾去不难（挺难）发现，最后的的序列类似 $x,x,...,x,a_{i},...,a_{j},x+k+1,x+k+1...$ ，发现这样可能最后与总数不相符，我们需要微调一下。发现上面总数单增，记总数为 $S(x)$ ，发现 $S(x)$ 单增，我们可以二分求出满足 $S(x)<=\sum a_{i}<S(x+1)$ 然后，多出来的分配给 $x$ (因为我们优先放到小的后面)，还不够就分配给 $x+k+1$ 因为懒，直接沾自己代码了(有的时候，看代码更易懂)

1
ll S(int l){
2
    ll r=1ll*(l+k);
3
    ll sum=0;
4
    for (int i=1;i<=n;i++){
5
        if (l<=a[i]&&a[i]<=r)b[i]=a[i],sum+=b[i];
6
        else if (a[i]<l)b[i]=l,sum+=b[i];
7
        else b[i]=r,sum+=b[i];
8
    }
9
    return sum;
10
}
11
void init(){
12
    scanf("%d%d",&n,&k);s=0;
13
    for (int i=1;i<=n;i++)scanf("%d",a+i),s+=1ll*a[i];
14
    std::sort(a+1,a+n+1);
15
}
16
void solve(){
17
    int l=a[1],r=a[n]-k;
18
    while (r-l>1){
19
        int mid=(l+r)>>1;
20
        if (S(mid)<=s)l=mid;
21
        else r=mid-1;
22
    }
23
    while (S(l)<=s)l++;l--;
24
    r=l+k;
25
    ll sum=S(l);
26
    for (int i=1;sum<s&&i<=n;i++)
27
        if (a[i]<=l)b[i]++,sum++;
28
    for (int i=1;sum<s&&i<=n;i++)
29
        if (a[i]>r)b[i]++,sum++;
30
    ll ans=0;
31
    for (int i=1;i<=n;i++){
32
        if (a[i]<b[i])ans+=1ll*(b[i]-a[i])*k;
33
        ans+=1ll*b[i]*(b[i]+1)/2;
34
    }
35
    printf("%lld\n",ans);
36
}