前言
今天给大家带来7.12的Codeforces Round #806 (Div. 4) G. Good Key, Bad Key的翻译及题解
感谢大家支持🤞
益题交流群：1019201086 (QQ)
作者： H_D_NULL
原题面
题目描述
你有 $n$ 个箱子。第 $i$ 个箱子中有 $a_i$ 个硬币。你需要按照从箱子 $1$ 号到箱子 $n$ 号的顺序打开所有 $n$ 个箱子。
你可以用以下两种钥匙之一打开一个箱子：
- 好钥匙：使用一次消耗 $k$ 个硬币。
- 坏钥匙：使用时不消耗硬币，但会使所有未打开的箱子中的硬币数减半（包括正要打开的这个箱子）。硬币减半时向下取整。比如，用坏钥匙打开箱子 $i$ 号时，$a_i=a_i/2$，$a_i+1=a_i+1/2$，$……$，$a_n=a_n/2$。
所有钥匙用过一次就会断掉（别想着买一把好钥匙开完所有箱子了），好钥匙需要重复付费，坏钥匙效果会重复计算。
也就是说，你总共需要使用 $n$ 把钥匙，每个箱子用一把。开始时，你没有硬币和钥匙，如果想用好钥匙，你就得去买。值得注意的是，在这个过程中你可以赊账买钥匙；例如，如果你只有 $1$ 个硬币，你也可以购买价值 $k=3$ 个硬币的好钥匙，你的余额会变成 $-2$ 个硬币。
你需要求出开完所有箱子之后你能获得的最大硬币数量（显然大于等于 $0$ ）。
INPUT
第一行包含一个整数 $t$（$1 \leq t \leq 10
^4$），表示测试数据的组数。
- 每组测试数据的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^5$，$0 \leq k \leq 10^9$），分别表示箱子的个数和每把好钥匙的花费。
- 每组测试数据的第二行包含 $n$ 个整数 $a_i$（$0 \leq a_i \leq 10^9$），表示每个箱子中硬币的数量。
所有测试数据中 $n$ 的总和不超过 $10^5$ 。
OUTPUT
对于每个测试数据，输出对应的可获得最大硬币数量。
提示（题面中给出）：开 $long$ $long$
解题思路：
暴力思想：
枚举每个箱子用钥匙的种类。时间复杂度：$O(2^n)$
无优化的DP思想：
维护 $f[i][j]$ 表示开完 $i$ 个箱子用了j把坏钥匙能获得的最大硬币数。状态转移方程：$f[i][j]=max(f[i-1][j-1]+ai\div2^j,f[i-1][j]+ai\div2^j-k)$。时间复杂度：$O(n^2)$
初步形成贪心思想：
因为坏钥匙可以对所有未打开箱子造成减半影响，所以我们模糊地感受到应该尽量晚地使用坏钥匙：
- 特别地，只有两个箱子且限定了需使用一次好钥匙，一次坏钥匙时，先使用好钥匙可获得 $a_1+a_2\div2-k$ ，先使用坏钥匙可获得 $(a_1+a_2\div2)-k$ 显然较前一种情况少。
- 一般地，如果好钥匙的数量确定，则好钥匙对数量的影响确定（与顺序无关），而坏钥匙越早使用对总数量的影响越大。
故得出贪心策略：先使用一定数量好钥匙，再使用坏钥匙开剩下的箱子。对于本题，则先枚举选用好钥匙的数量 $num$（$1\leq num\leq n$），再按上述策略计算每次的数量，从中取最大值。
接下来证明时间复杂度：枚举使用好钥匙数量 $num$：$O(n)$；计算好钥匙部分的数量，利用预处理的前缀和数组 $s$ ，结果 $s[num]-num\ast k$：$O(1)$；计算坏钥匙部分的数量，模拟得第一把坏钥匙开出的箱子得 $\frac{a_i}{2}$ ，第二把为 $\frac{a_i+1}{4}$ ，以此类推，当所有坏钥匙都减半至 $0$ 后可提前跳出，最坏复杂度 $O(\log_{2}a_{max})$。
总上，按以上策略贪心总时间复杂度 $O(n\log_{2}a_{max})$ ，对于极限数据能一秒内跑过（剩下的两秒就借给常数吧），通过此题绰绰有余。
//CF赛时实际运行用时62ms
using namespace std;
//不建议使用
int a[100005];
int s[100005]; //前缀和，O(1)得好钥匙花费
signed main(){
ios::sync_with_stdio(false);
re int T,n,k;
cin>>T;
while(T--){
cin>>n>>k;
re int maxx=0;
re int slen=0; //记录max{a}
for(re int i=1;i<=n;i++){
cin>>a[i];
s[i]=a[i]+s[i-1];
slen=max(slen,a[i]);
}
for(re int i=0,sum;i<=n;i++){
re int ans=s[i]-(i*k); //好钥匙总贡献
sum=1; //记录减半的倍数
for(re int j=i+1,nw;j<=n&&sum<=slen;j++){
//减半倍数超过max{a}时后面的箱子都被减为0，不再统计
sum<<=1;
nw=a[j];
nw/=sum;
ans+=nw;
}
maxx=max(maxx,ans); //更新答案
}
cout<<maxx<<"\n";
}
return 0;
}
这期到这里就结束了，我们下期再见！😊
益题交流群：1019201086 (QQ)
发布时间： 2022-07-21
最后更新： 2022-07-21
本文标题： 21. Codeforces Round #806 (Div. 4) G翻译及题解
本文链接： https://yitee.top/posts/24569.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！
