$$\mathrm{涨薪}$$

题目链接：$\mathrm{n}\mathrm{o}\mathrm{w}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{r}212913$

到牛客看

——>点我跳转<——

题目

公司中总共有 $n$ 个人，其中第 $i$ 个人的初始工资为 $a_i$。公司根据每个人的绩效(工作表现)来评定每个人的涨薪幅度。每年有 $x$ 个人绩效为 A，工资可以变为原来的 $3$ 倍；$y$ 个人绩效为 B，工资可以变为原来的 $2$ 倍，其余人绩效为 C，工资不变，连续两年绩效为 C 会被开除。(保证 $x+y\le n$)

假如公司没有一直招聘新员工，请问 $m$ 年后，公司需要给所有在职员工支付的工资总和最多为多少。由于答案可能很大，请输出对 $10^9+7$ 取模后的结果。

输入

输入第一行包含四个正整数 $n,m,x,y$，意义如题面所示。 接下来一行包含 $n$ 个正整数，第 $i$ 个正整数为 $a_i$ 代表第 $i$ 个人的初始工资。

输出

输出一行一个整数表示 $m$ 年后工资总和对 $10^9+7$ 取模后的结果。

样例输入1

2 1 1 1 5 3

样例输出1

21

样例输入2

2 2 0 0 5 2

样例输出2

0

数据范围

对于 $20\%$ 的数据范围，满足 $n\le 10,m\le 10,a_i\le 10$ 对于 $40\%$ 的数据范围，满足 $n\le 10^5,m\le 10,a_i\le 10^5$ 对于另外 $20\%$ 的数据范围，满足 满足 $n\le 10^5,m\le 10,a_i\le 10^5$ 且 $x+y=n$ 对于另外 $20\%$ 的数据范围，满足 满足 $n\le 10^5,m\le 10^9,a_i\le 10^5$ 且 $x+y=n$ 对于 $100\%$ 的数据范围，满足 $1\le n\le 10^5,1\le m\le 10^9,1\le a_i\le 10^5$

思路

这道题是一道贪心。

我们可以发现，我们一直把 A 给初始值最大的那些人，把 B 给初始值接着大的人是最优的。 至于别的人，被开除也无所谓（好惨

求 A 类人和 B 类人的贡献就先用快速幂求出每类人增长的倍数，然后乘上去即可。

有一个细节，就是如果年数小于 $2$ 年的话 C 类人不会被开除，就还要算上它们的。

比赛时

看出来了，就码出来了。

代码

#include<cstdio> #include<iostream> #include<algorithm> #define ll long long #define mo 1000000007 using namespace std; ll n, m, x, y, a[100001], Asum, Bsum, Esum, mi3, mi2, re, zhengfu; char c; ll read() { re = 0; zhengfu = 1; c = getchar(); while ((c < '0' || c > '9') && c != '-') c = getchar(); if (c == '-') { zhengfu = -1; c = getchar(); } while (c >= '0' && c <= '9') { re = re * 10 + c - '0'; c = getchar(); } return re * zhengfu; } bool cmp(ll x, ll y) { return x > y; } ll ksm(ll x, ll y) {//快速幂 re = 1; while (y) { if (y & 1) re = (re * x) % mo; x = (x * x) % mo; y >>= 1; } return re; } int main() { n = read(); m = read(); x = read(); y = read(); for (ll i = 1; i <= n; i++) a[i] = read(); mi3 = ksm(3, m);//预处理出翻的倍数 mi2 = ksm(2, m); sort(a + 1, a + n + 1, cmp);//从大到小排序 for (ll i = 1; i <= x; i++)//最前面的（最大的）绩效为 A Asum = (Asum + (a[i] * mi3) % mo) % mo; for (ll i = x + 1; i <= x + y; i++)//接着（接着大的）就是绩效为 B Bsum = (Bsum + (a[i] * mi2) % mo) % mo; if (m < 2)//只有年数小于两年，这些 C 的才不会被开除，才要记录 for (ll i = x + y + 1; i <= n; i++) Esum = (Esum + (a[i] * m) % mo) % mo; printf("%lld", (Asum + Bsum + Esum) % mo); return 0; }