Skills

题目描述

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;
}