Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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.
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月20日 星期六 13时11分30秒
4File Name :code/cf/#339/D.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34LL n,A,cf,cm,m;
35LL b[N];
36LL c[N]; //c[i]表示将i个变为最大值需要的最少花费
37LL sum[N] ; //sum[i]表示花费最少的i个的价值和
38struct node
39{
40 LL val;
41 int id;
42
43 bool operator < (node b)const
44 {
45 return val>b.val;
46 }
47}a[N];
48
49bool cmp (LL a,LL b)
50{
51 return a<b;
52}
53bool cmp2( node a,node b)
54{
55 return a.id<b.id;
56}
57int main()
58{
59 #ifndef ONLINE_JUDGE
60 freopen("code/in.txt","r",stdin);
61 #endif
62 ios::sync_with_stdio(false);
63 cin>>n>>A>>cf>>cm>>m;
64 for ( int i = 1 ; i <= n ; i++) cin>>a[i].val,a[i].id = i,b[i] = a[i].val;
65 sort(b+1,b+n+1,cmp);
66 sort(a+1,a+n+1);
67
68 LL cost = 0 ;
69 c[0] = 0;
70 for ( int i = 1 ; i <= n ; i++)
71 {
72 cost +=A-a[i].val;
73 c[i] = cost;
74 }
75 sum[0] = 0LL;
76 for ( int i = 1 ; i <= n ; i++) sum[i] = sum[i-1] + b[i];
77
78 LL maxnum;
79 LL minval;
80 LL ans = -1;
81 for ( int i = 0 ; i <= n ; i++) //i表示达到最大值的有i个
82 {
83 LL M = m;
84 LL left = M - c[i];
85 if (left<0) break;
86
87 LL l=0,r=A;
88
89 while (l<r) //在剩下的n-i个数里二分最小值
90 {
91 LL mid = (l+r+1)>>1;
92 int x= lower_bound(b+1,b+n-i+1,mid)-b-1;
93 if (mid*x-sum[x]<=left) l = mid;
94 else r = mid -1;
95 }
96
97 if (cf*i+cm*l>ans)
98 {
99 ans = cf*i+cm*l;
100 maxnum = i;
101 minval = l;
102 }
103 }
104
105 for ( int i = 1 ; i <= maxnum ; i++) a[i].val = A;
106 for ( int i = 1 ; i <= n ; i++) if (a[i].val<minval) a[i].val = minval;
107 sort(a+1,a+n+1,cmp2);
108 cout<<ans<<endl;
109 for ( int i = 1 ; i <= n-1 ; i++) cout<<a[i].val<<" ";
110 cout<<a[n].val<<endl;
111
112 #ifndef ONLINE_JUDGE
113 fclose(stdin);
114 #endif
115 return 0;
116}