Codeforces Round 916 (Div. 3) C. Quests （贪心 + 模拟）
Monocarp 正在玩一款电脑游戏。为了提升角色等级，他可以完成任务。游戏中有 n 个任务，编号从 1 到 n 。
Monocarp 可以按照以下规则完成任务：
-
1 -st任务总是可以完成的；如果所有任务 j<i 都至少完成了一次，那么 i (-th)任务就可以完成。请注意，独角仙可以多次完成同一个任务。
-
每次完成任务，角色都会获得一定数量的经验值：
第一次完成 i -th任务，获得 a i a_i ai 经验值；之后每完成一次 i \th任务，就能获得 b i b_i bi 点经验值。
Monocarp 是个大忙人，所以他有空闲时间完成的任务不超过 k 个。你的任务是计算 Monocarp 在完成不超过 k 个任务的情况下可能获得的最大总经验值。
输入
第一行包含一个整数 t ( 1 ≤ t ≤ 1 0 4 ) t ( 1≤t≤10^4 ) t(1≤t≤104) - 测试用例数。
每个测试用例的第一行包含两个整数 n 和 k ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ; 1 ≤ k ≤ 2 ⋅ 1 0 5 ) k ( 1≤n≤2⋅10^5 ; 1≤k≤2⋅10^5 ) k(1≤n≤2⋅105;1≤k≤2⋅105)–分别是任务数和 Monocarp 能完成的最大任务数。
第二行包含 n n n 个整数 a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 1 0 3 ) a_1,a_2,…,a_n ( 1≤a_i≤10^3 ) a1,a2,…,an(1≤ai≤103)。
第三行包含 n n n 个整数 b 1 , b 2 , … , b n ( 1 ≤ b i ≤ 1 0 3 ) b_1,b_2,…,b_n ( 1≤b_i≤10^3 ) b1,b2,…,bn(1≤bi≤103)。
输入的其他限制条件：所有测试用例中 n 的总和不超过 2 ⋅ 1 0 5 2⋅10^5 2⋅105 。
输出
对于每个测试用例，打印一个整数–如果单卡完成的任务不超过 k ，单卡可能获得的最大总经验值。
考虑所有的选法有哪些 ？
假如现在我们做到了第m个任务，如果要在这m个任务里选，我们肯定选重复做的时候获得的经验最多的那一个任务。
那么这时候获得的经验就是 ∑ i = 1 m a i + ∑ i = 1 k − m b m a x \sum \limits_{i = 1} \limits^{m}a_i + \sum \limits_{i=1} \limits^{k-m}b_{max} i=1∑mai+i=1∑k−mbmax 。
只要扫遍整个序列，然后维护一个 b m a x b_{max} bmax，就可以取出在这所有最优情况里面的最优解。
CODE：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;int a[N];
int b[N];void solve(){int n,k;cin >> n >> k;for(int i = 1;i <= n;i++)cin >> a[i];for(int i = 1;i <= n;i++)cin >> b[i];int sum = 0;int MM = 0;int res = 0;for(int i = 1;i <= min(k,n);i++){sum += a[i];MM = max(MM,b[i]);res = max(res,sum + MM*(k - i));} cout << res << endl;
}int main(){int T;cin >> T;while(T--){solve();}return 0;
}