#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],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 max_b=0;
int ans=0;
for(int i=1;i<=n;i++)
{
sum+=a[i];
max_b=max(max_b,b[i]);
if(i<=k)
ans=max(ans,max(0,k-i)*max_b+sum);
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
该题我没想出来,知道该题是一个贪心,但是有一个点没想到,就是 b 其实只会选一次,选一个最大的,然后一直用这个最大的 b
相当于我们打游戏刷任务,只有解锁前面的才能玩后面的关卡,但是我们不知道每一个的经验值,人类可以一眼看到全局,但是计算机贪心计算只可以一个一个数字去遍历
所以其实就是第一个通关的经验值的和,再加上维护的最大值的经验值乘以剩下的次数
相当于两次贪心,第一次是维护 b 的最大值,第二次是维护答案的最大值
max(0,k-i) 的意思是,乘的次数一定大于等于零,否则没有实际意义
所以该题的关键是把式子想清楚,就是 s[a]+(k-i)*max_b
前面 i 个 a 的和加上 k-i 个 b 的最大值的和,就是最后的答案