P10387 [蓝桥杯 2024 省 A] 训练士兵

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[当前轮数]，即可得到下一轮参与训练士兵的总费用。
复杂度分析

代码实现

[code]void solve(){    LL n,S;    cin>>n>>S;    vectorc(n);    vectorp(n);    int mx=0;    LL  res=0,cur=0;    rep(i,0,n){        cin>>p>>c;        mx=max(mx,c);        cur+=p;    }    vectorloss(mx+1,0);//  总练习次数相同的士兵各单练一次的花费        rep(i,0,n){        loss[c]+=p;    }    rep(i,1,mx+1){        res+=min(S,cur);        cur-=loss;    }    cout