题意
给你n个数，可以花费1使得数字+1，最大加到A，最多花费m。最后，n个数里的最小值为min，为A的有k个，给你cm和cf，求force=min*cm+k*cf 的最大值，和n个数操作后的结果。
分析
我们如果要让最小值增加，那它加到和第二小的一样时，就有两个最小值，接下来就要两个一起增加。。到后来就要好多个一起增加了。
那么我们可以枚举加到A的有多少个，然后用二分的方法求剩下m元，可以使最小值最大为多少。
怎么二分呢？
l=0，r=A。mid=（l+r）/2。
我们假设现在是最小值为mid，那算出有多少个比 mid 小的，然后可以得出花费，如果花费比m大，那说明mid太大了，于是 r=mid-1，然后继续查找。如果花费比m小，那就可能mid太小了，先保存起来，然后 l=mid+1 继续查找。
在算有多少个比mid小时，也可以用二分。比如假如 mmid 个比 mid 小，然而 a[mmid]>mid , 那就 mmid 太大了....也可以用 lower_bound 函数。
于是我们具体的做法是：用结构体存下值和序号，先按值从小到大排序，然后求前缀和，枚举有 i 个加到 A ，算出花费，m减去这个花费剩下的拿去提升最小值，二分确定最小值的最大值，然后更新答案。
代码
#include<bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std; struct data
{
ll id,v;
} a[N]; bool cmp(data a,data b)
{
return a.v<b.v||a.v==b.v&&a.id<b.id;
} ll n,A,cf,cm,m;
ll L,ans[N],f,ansA,ansL;
ll s[N]; ll findL(ll m,ll R)//还剩多少m，右端点是什么
{
ll l=,r=A,ans=;//二分确定最小值的值 while(l<=r)
{ ll mid=(r+l)>>; //二分确定有多少个比这个值小，然后计算需要的花费
int p=lower_bound(a+,a++n,(data){,mid},cmp)-a-;
if(p>R)p=R;
if(p*mid-s[p]<=m)
{
ans=mid;
l=mid+;
}
else
r=mid-;
}
return ans;
}
int main()
{
scanf("%lld%lld%lld%lld%lld",&n,&A,&cf,&cm,&m);
for(int i=; i<=n; i++)
{
scanf("%lld",&a[i].v);
a[i].id=i;
} sort(a+,a+n+,cmp);//先排序再求前缀和
for(int i=; i<=n; i++)
s[i]=s[i-]+a[i].v; for(int i=; i<=n; i++) //如果有i个设置为A的话
{ ll p=A*i-s[n]+s[n-i];//花费
if(p<=m)
{
L=findL(m-p,n-i);//那最小值可以达到多少
if(cm*L+cf*i>f) //更新答案
{
f=cm*L+cf*i;
ansA=i;//储存有几个变成A
ansL=L;//储存最小值要达到多少
}
}
}
printf("%lld\n",f);
for(int j=; j<=n; j++)
{
if(j>n-ansA)
ans[a[j].id]=A;
else if(a[j].v<=ansL)
ans[a[j].id]=ansL;
else
ans[a[j].id]=a[j].v;
}
for(int i=; i<=n; i++)
printf("%lld ",ans[i]);
return ;
}