题目链接：https://ac.nowcoder.com/acm/problem/212913

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109226431

题目

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

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

输入

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

输出

输出一行一个整数表示 年后工资总和对 取模后的结果。

样例输入1

2 1 1 1
5 3

样例输出1

21

样例输入2

2 2 0 0
5 2

样例输出2

0

数据范围

对于 的数据范围，满足
对于 的数据范围，满足
对于另外 的数据范围，满足 满足 且
对于另外 的数据范围，满足 满足 且
对于 的数据范围，满足

思路

这道题是一道贪心。

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

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

有一个细节，就是如果年数小于 年的话 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, ***;
char c;

ll read() {
    re = 0;
    *** = 1;
    c = getchar();
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    if (c == '-') {
        *** = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        re = re * 10 + c - '0';
        c = getchar();
    }
    return re * ***;
}

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