题目描述
Lesha plays the recently published new version of the legendary game hacknet. In this version character skill mechanism was introduced. Now, each player character has exactly $n$ skills. Each skill is represented by a non-negative integer $a_i$ — the current skill level. All skills have the same maximum level $A$.
Along with the skills, global ranking of all players was added. Players are ranked according to the so-called Force. The Force of a player is the sum of the following values:
- The number of skills that a character has perfected (i.e., such that $a_i=A$), multiplied by coefficient $c_f$.
- The minimum skill level among all skills ($\min(a_i)$), multiplied by coefficient $c_m$.
Now Lesha has m hacknetian currency units, which he is willing to spend. Each currency unit can increase the current level of any skill by $1$ (if it’s not equal to $A$ yet). Help him spend his money in order to achieve the maximum possible value of the Force.
题意概述
给定$n$个技能,第$i$个技能的等级为$a_i$。所有技能的最高等级为$A$。你有$m$个技能点,每个技能点可以让某个技能升$1$级。给定两个数$c_f, c_m$,定义所有技能的价值总和为$c_f$乘满级技能的个数加$c_m$乘所有技能的最低等级。求价值总和的最大值。
数据范围:$1 \le n \le 10^5, \; 1 \le A \le 10^9, \; 0 \le c_f, c_m \le 1000, \; 0 \le m \le 10^{15}$。
算法分析
将技能按等级从小到大排序。记录两个指针$p, q$,$p$指针之后的技能都已满级,$q$指针之前的技能的等级极差不大于$1$。先计算出$p$的最小值,接着依次枚举$p$,同时根据贪心策略,前$q$个技能的等级越平均越好。这样就可以计算出答案。
代码
#include <iostream> #include <algorithm> using namespace std; struct skill { long long a, id; } s[100002]; bool cmp1(skill a, skill b) { return a.a < b.a; } bool cmp2(skill a, skill b) { return a.id < b.id; } long long n, A, cf, cm, m, ans, pnt, cnt, rec[3], pre[100002], suf[100002]; int main() { cin >> n >> A >> cf >> cm >> m; for (int i = 1; i <= n; ++i) { cin >> s[i].a; s[i].id = i; } sort(s + 1, s + n + 1, cmp1); for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + s[i].a; for (int i = n; i; --i) suf[i] = suf[i + 1] + s[i].a; cnt = 0, pnt = n, rec[0] = n + 1; while (pnt > 0 && (n - pnt + 1) * A - suf[pnt] <= m) --pnt; for (++pnt; pnt <= n + 1; ++pnt) { long long rem = m - (n - pnt + 1) * A + suf[pnt]; while (cnt < pnt && s[cnt].a * cnt - pre[cnt] <= rem) ++cnt; --cnt; if (cnt) (rem -= s[cnt].a * cnt - pre[cnt]) /= cnt; else rem = 1e18; if (ans < (n - pnt + 1) * cf + min((s[cnt].a + rem), A) * cm) { ans = (n - pnt + 1) * cf + min((s[cnt].a + rem), A) * cm; rec[0] = pnt, rec[1] = cnt, rec[2] = min((s[cnt].a + rem), A); } } for (int i = 1; i <= rec[1]; ++i) s[i].a = rec[2]; for (int i = rec[0]; i <= n; ++i) s[i].a = A; sort(s + 1, s + n + 1, cmp2); cout << ans << endl; for (int i = 1; i <= n; ++i) cout << s[i].a << ' '; cout << endl; return 0; }