给你n个数，可以花费1使得数字+1，最多花费m，最后，n个数里的最小值为min，为A的有k个，那么force=min*cm+k*cf。求force最大值，和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=0,r=A,ans=0;//二分确定最小值的值
while(l<=r)
{
ll mid=(r+l)>>1;
//二分确定有多少个比这个值小，然后计算需要的花费
int p=lower_bound(a+1,a+1+n,(data){0,mid},cmp)-a-1;
if(p>R)p=R;
if(p*mid-s[p]<=m)
{
ans=mid;
l=mid+1;
}
else
r=mid-1;
}
return ans;
}
int main()
{
scanf("%lld%lld%lld%lld%lld",&n,&A,&cf,&cm,&m);
for(int i=1; i<=n; i++)
{
scanf("%lld",&a[i].v);
a[i].id=i;
}
sort(a+1,a+n+1,cmp);//先排序再求前缀和
for(int i=1; i<=n; i++)
s[i]=s[i-1]+a[i].v;
for(int i=0; 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=1; 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=1; i<=n; i++)
printf("%lld ",ans[i]);
return 0;
}
原文：http://www.cnblogs.com/flipped/p/5196559.html