题面

解题思路

推理+二分+解方程

分析

这手操作有点骚

我们首先可以分析一手这个函数有什么性质

有点小头秃，但是我们可以分析一手单个函数的变化

不难发现，$b_i(a_i-b_i^2)$ 随着 $b_i$ 变化的增量是单调递减的

令 $f(b)=b(a-b^2),f(b+1)=(b+1)(a-(b+1)^2)$，

整理可得：

对称轴为 $x=\frac 1 2$，也就是这个函数是在 $\Z ^+$ 上单调递减（不含 $0$ )，

这样子就启发我们，可以把这个函数拆开看，就等同于 现在有 $n$ 堆数，要从中取出 $K$ 个数使得结果最大

这样一下子贪心显然是成立的，但是如果一个个取的话……

这个时候我们就可以请出我们的二分了！

不难想到我们可以二分 选中的数的最小值，显然这东西是单调的

即，最小值越小，越有可能选出 $K$ 个， 大则相反

然后瓶颈就转向了如何求出每堆中要选几个

我们可以把 $f(b+1)-f(b)$ 记为 $g(b)=-3b^2-3b+a-1$，

只需解 $g(b)=-3b^2-3b+a-1\ge mid$ （ $mid$ 为二分的最小值），即可

由求根公式可得，$\large x=\lfloor \frac {3-\sqrt{9+4(a-1-mid)}} {-6}\rfloor$

最后要我们输出方案，也可以这么求，但是要注意的是，可能我们选的数总和会超出 $K$，因为有些数会卡在最小值那个线上

我们只要判断一下去掉即可

于是就做完了

Warning

1、别忘了 long long

2、注意求根无解的状况

3、注意精度

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 100007
using namespace std;
const long double A=-3,B=-3;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline LL read() {
    rll s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
LL n,a[N],l,r,m,K,sum,Ans[N],ans;
inline LL calc(long double C) {//求根
    if(A+B+C<0) return 0;
    return (-B-sqrt(B*B-4*A*C))/(2*A);
}
inline LL solve(rll m) {//判断是否满足K个
    sum=0;
    for(rint i=1;i<=n;i++) sum+=min(calc(a[i]-1-m),a[i]);
    return sum;
}
inline void work_out(rll m) {
    sum=0;
    for(rint i=1;i<=n;i++) sum+=Ans[i]=min(calc(a[i]-1-m),a[i]);
}
int main() {
    rint i;n=read(),K=read(),l=inf;
    for(i=1;i<=n;i++) a[i]=read(),cmax(r,a[i]),cmin(l,a[i]-3*a[i]*a[i]-3*a[i]-1);
    while(l<=r) {
        m=(l+r)>>1;
        if(solve(m)>=K)    ans=m,l=m+1;
        else r=m-1;
    }work_out(ans);
    for(i=1;i<=n;i++) {
        if(sum>K&&a[i]-3*Ans[i]*Ans[i]-3*Ans[i]-1==ans) --Ans[i],--sum;//判掉多出的
        printf("%lld ",Ans[i]);
    }
    return 0;
}

devil.