P10387 [蓝桥杯 2024 省 A] 训练士兵
原题链接
题目范围
\(1 \leq n \leq 10^5\)，\(1 \leq p_i, c_i \leq 10^6\)，\(1 \leq S \leq 10^{10}\)
解题思路
在每一轮训练中，所有仍需训练的士兵都会参与。这一轮只有两种选择：
- 进行一次组团训练，花费为 \(S\)；
- 所有参与的士兵各自单独训练一次，花费为当前这些士兵的 \(p_i\) 之和，记为
cur。
因此每一轮的最优花费为 \(\min(S, \text{cur})\)。
关键在于如何维护 cur。
当某个士兵需要训练 \(c_i\) 次时，他会参与前 \(c_i\) 轮训练，并在第 \(c_i\) 轮结束后完成训练，从下一轮开始不再参与。
因此可以预处理数组 loss，其中 loss[x] 表示所有满足 \(c_i = x\) 的士兵，其 \(p_i\) 之和。
初始时，cur 为所有士兵的 \(p_i\) 之和。每一轮结束后，将 cur 减去 loss[当前轮数]，即可得到下一轮参与训练士兵的总费用。
复杂度分析
代码实现
void solve(){LL n,S;cin>>n>>S;vector<int>c(n);vector<int>p(n);int mx=0;LL res=0,cur=0;rep(i,0,n){cin>>p[i]>>c[i];mx=max(mx,c[i]);cur+=p[i];}vector<LL>loss(mx+1,0);// 总练习次数相同的士兵各单练一次的花费rep(i,0,n){loss[c[i]]+=p[i];}rep(i,1,mx+1){res+=min(S,cur);cur-=loss[i];}cout<<res<<'\n';
}