Codeforces

Luogu

分析

对 $f_i(x)=x(a_i-x^2)$ 求二阶导可以发现它是凸的，那么每次选一个 $\Delta y$ 最大的放一定是最优的。

我们二分最小的 $\Delta y$，对每个函数二分（或者直接解一元二次方程）找到它被加的次数，判断是否 $\leq k$ 即可。

这样子最后可能并不能达到 $k$，把还没加的部分选加到 $\Delta y$ 最大的那些上即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,a[N],p[N]; ll k,b[N];

ll f(int i,ll x) {
    return x>=a[i]+1?-5e18:-3*x*x+3*x+a[i]-1;
}

ll check(ll lim) {
    ll res=0;
    for (int i=1;i<=n;++i) {
        ll L=0,R=a[i];
        while (L<R) {
            ll mid=(L+R+1)>>1;
            if (f(i,mid)>=lim) L=mid;
            else R=mid-1;
        }
        res+=(b[i]=L);
    }
    if (res<=k) return res;
    else return 0;
}

int main() {
    n=read(),k=read(); ll L=5e18,R=-5e18;
    for (int i=1;i<=n;++i)
        a[i]=read(),L=min(L,f(i,a[i])),R=max(R,f(i,1));
    while (L<R) {
        ll mid=(L+R)>>1;
        if (check(mid)) R=mid;
        else L=mid+1;
    }
    ll cnt=check(L);
    for (int i=1;i<=n;++i) p[i]=i;
    sort(p+1,p+n+1,[](int x,int y) {
        return f(x,b[x]+1)>f(y,b[y]+1);
    });
    for (int i=1;i<=k-cnt;++i) ++b[p[i]];
    for (int i=1;i<=n;++i) printf("%lld ",b[i]); puts("");
    return 0;
}