题目描述 公司中总共有 n 个人，其中第 i 个人的初始工资为 a i a_i ai 。公司根据每个人的绩效(工作表现)来评定每个人的涨薪幅度。每年有 x 个人绩效为 A，工资可以变为原来的 3 倍；y 个人绩效为 B，工资可以变为原来的 2 倍，其余人绩效为 C，工资不变，连续两年绩效为 C 会被开除。(保证 x + y ≤ n x+y≤n x+y≤n)
假如公司没有一直招聘新员工，请问 m 年后，公司需要给所有在职员工支付的工资总和最多为多少。由于答案可能很大，请输出对 1 0 9 + 7 10^9+7 109+7 取模后的结果。
输入描述: 输入第一行包含四个正整数 n , m , x , y n, m,x,y n,m,x,y，意义如题面所示。 接下来一行包含 n 个正整数，第 i 个正整数为 a i a_i ai代表第 i 个人的初始工资。
输出描述: 输出一行一个整数表示 m 年后工资总和对 1 0 9 + 7 10^9+7 109+7 取模后的结果。
示例1 输入 2 1 1 1 5 3
输出 21
示例2 输入 2 2 0 0 5 2
输出 0
备注: 对于 20 20 20% 的数据范围，满足 n ≤ 10 , m ≤ 10 , a i ≤ 10 n≤10,m≤10,a_i≤10 n≤10,m≤10,ai≤10
对于 40 40 40% 的数据范围，满足 n ≤ 1 0 5 , m ≤ 10 , a i ≤ 1 0 5 n≤10^5 ,m≤10,a_i≤10^5 n≤105,m≤10,ai≤105
对于另外 20 20 20% 的数据范围，满足 满足 n ≤ 1 0 5 , m ≤ 10 , a i ≤ 1 0 5 n≤10^5 ,m≤10,a_i ≤10^5 n≤105,m≤10,ai≤105且 x + y = n x+y=n x+y=n
对于另外 20 20 20% 的数据范围，满足 满足 n ≤ 105 , m ≤ 109 , a i ≤ 1 0 5 n≤10 5 ,m≤10 9 ,a_i ≤10^5 n≤105,m≤109,ai≤105且 x + y = n x+y=n x+y=n
对于 100 100 100% 的数据范围，满足 1 ≤ n ≤ 105 , 1 ≤ m ≤ 1 0 9 , 1 ≤ a i ≤ 1 0 5 1≤n≤10 5 ,1≤m≤10^9 ,1≤a_i≤10^5 1≤n≤105,1≤m≤109,1≤ai≤105
解题思路 贪心易得,绩效得C 的人一定是初始薪资最少的人。
其余的人进行排序，最大的x个和次大的y个分别乘3和2，其余的都不要；
因为有m天，每天都是乘同样的数，所以快速幂；
代码
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std; const long long INF=1e9+7; long long n,m,x,y,a[110000],t,tt; long long ans1,ans2,sum; bool cmp(int x,int y) { return x>y; } long long poww(long long a ,long long b) { long long ans = 1 ; long long base = a % INF; while(b>0) { if(b&1!=0) ans = (ans*base)%INF; base=(base*base)%INF; b>>=1; } return ans; } int main() { scanf("%lld%lld%lld%lld",&n,&m,&x,&y); t=poww(2,m); tt=poww(3,m); for(int i=1; i<=n; i++) scanf("%lld",&a[i]); sort(a+1,a+n+1,cmp); for(int i=1; i<=x; i++) ans1=(ans1+a[i]*tt%INF)%INF; for(int i=x+1; i<=x+y; i++) ans2=(ans2+a[i]*t%INF)%INF; for(int i=x+y+1; i<=n; i++) sum=(sum+a[i])%INF; if(m<2) printf("%lld",((ans1+ans2)%INF+sum)%INF); else printf("%lld",((ans1+ans2)%INF)%INF); }