codeforces #339 div2 D

http://codeforces.com/contest/613/problem/B 题意：有n个技能，初始每个技能的level为a[i]，每个技能最大level为A(不妨称为满级技能)，设满级技能个数为maxnum,最小的技能level为minval,问如何将m个技能点分配到n个技能上使得cfmaxsum+cmminval (n<=1E5,a[i],A<=1E9,cf,cm<=1E3,m<=1E15)

思路：贪心。如果让有限的maxsum个技能满级的话，那么一定是让初始最大的maxsum技能满级更优。我们O(n)可以预处理一个c[i]数组，表示将i个技能变成最大值的最小花费。

然后再预处理一个前缀和数组，sum[i]表示初始最小的i个的技能的花费之和。

然后从0到n枚举变成最大值的技能的个数，在剩下的技能中二分能达到的最小值。

注意要按照原来顺序输出，所以记得记录id.

/* ***********************************************
Author :111qqz
Created Time :2016年02月20日 星期六 13时11分30秒
File Name :code/cf/#339/D.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
LL n,A,cf,cm,m;
LL b[N];
LL c[N]; //c[i]表示将i个变为最大值需要的最少花费
LL sum[N] ; //sum[i]表示花费最少的i个的价值和
struct node
{
    LL val;
    int id;

    bool operator < (node b)const
    {
	return val>b.val;
    }
}a[N];

bool cmp (LL a,LL b)
{
    return a<b;
}
bool cmp2( node a,node b)
{
    return a.id<b.id;
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	ios::sync_with_stdio(false);
	cin>>n>>A>>cf>>cm>>m;
	for ( int i = 1 ; i <= n ; i++) cin>>a[i].val,a[i].id =  i,b[i] = a[i].val;
	sort(b+1,b+n+1,cmp);
	sort(a+1,a+n+1);
	
	LL cost = 0 ;
	c[0] = 0;
	for ( int i = 1 ; i <= n ; i++)
	{
	    cost +=A-a[i].val;
	    c[i] = cost;
	}
	sum[0] = 0LL;
	for ( int i = 1 ; i <= n ; i++) sum[i] = sum[i-1] + b[i];

	LL maxnum;
	LL minval;
	LL ans = -1;
	for ( int i = 0 ; i <= n ; i++) //i表示达到最大值的有i个
	{
	    LL M = m;
	    LL left = M - c[i];
	    if (left<0) break;

	    LL l=0,r=A;
	    
	    while (l<r) //在剩下的n-i个数里二分最小值
	    {
		LL mid = (l+r+1)>>1;
		int x= lower_bound(b+1,b+n-i+1,mid)-b-1;
		if (mid*x-sum[x]<=left) l = mid;
		else r = mid -1;
	    }

	    if (cf*i+cm*l>ans)
	    {
		ans = cf*i+cm*l;
		maxnum  = i;
		minval = l;
	    }
	}

	for ( int i = 1 ; i <= maxnum ; i++) a[i].val = A;
	for ( int i = 1 ; i <= n ; i++) if (a[i].val<minval) a[i].val = minval;
	sort(a+1,a+n+1,cmp2);
	cout<<ans<<endl;
	for ( int i = 1 ; i <= n-1 ; i++) cout<<a[i].val<<" ";
	cout<<a[n].val<<endl;

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}