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
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7LL n,A,cf,cm,m;
8LL b[N];
9LL c[N]; //c[i]表示将i个变为最大值需要的最少花费
10LL sum[N] ; //sum[i]表示花费最少的i个的价值和
11struct node
12{
13 LL val;
14 int id;
1 bool operator < (node b)const
2 {
3 return val>b.val;
4 }
5}a[N];
1bool cmp (LL a,LL b)
2{
3 return a<b;
4}
5bool cmp2( node a,node b)
6{
7 return a.id<b.id;
8}
9int main()
10{
11 #ifndef ONLINE_JUDGE
12 freopen("code/in.txt","r",stdin);
13 #endif
14 ios::sync_with_stdio(false);
15 cin>>n>>A>>cf>>cm>>m;
16 for ( int i = 1 ; i <= n ; i++) cin>>a[i].val,a[i].id = i,b[i] = a[i].val;
17 sort(b+1,b+n+1,cmp);
18 sort(a+1,a+n+1);
1 LL cost = 0 ;
2 c[0] = 0;
3 for ( int i = 1 ; i <= n ; i++)
4 {
5 cost +=A-a[i].val;
6 c[i] = cost;
7 }
8 sum[0] = 0LL;
9 for ( int i = 1 ; i <= n ; i++) sum[i] = sum[i-1] + b[i];
1 LL maxnum;
2 LL minval;
3 LL ans = -1;
4 for ( int i = 0 ; i <= n ; i++) //i表示达到最大值的有i个
5 {
6 LL M = m;
7 LL left = M - c[i];
8 if (left<0) break;
LL l=0,r=A;
1 while (l<r) //在剩下的n-i个数里二分最小值
2 {
3 LL mid = (l+r+1)>>1;
4 int x= lower_bound(b+1,b+n-i+1,mid)-b-1;
5 if (mid*x-sum[x]<=left) l = mid;
6 else r = mid -1;
7 }
1 if (cf*i+cm*l>ans)
2 {
3 ans = cf*i+cm*l;
4 maxnum = i;
5 minval = l;
6 }
7 }
1 for ( int i = 1 ; i <= maxnum ; i++) a[i].val = A;
2 for ( int i = 1 ; i <= n ; i++) if (a[i].val<minval) a[i].val = minval;
3 sort(a+1,a+n+1,cmp2);
4 cout<<ans<<endl;
5 for ( int i = 1 ; i <= n-1 ; i++) cout<<a[i].val<<" ";
6 cout<<a[n].val<<endl;
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}