题解 CF1119G 【Get Ready for the Battle】

搬运一下[CF官方题解](https://codeforces.com/blog/entry/66411) 最好的情况是除最后一次外都不浪费士兵，因此次数为$\lceil \frac{\sum\nolimits_{i=1}^n{hp}_{i}}{n} \rceil$ 考虑构造。首先一开始让所有人打第一个敌人，只要他的血量$<n$了，假设我们有一些兵团的士兵数量总和刚好为敌人剩余血量$k_1$,那么我们就让这些士兵去打敌人1，其余人在同一回合内去打敌人2.然后所有人再去打敌人2. 当敌人2血量$<n$时，假设我们又有一些兵团的士兵数量总和刚好为敌人剩余血量$k_2$，那么我们就让这些士兵去打敌人2，其余人在同一回合去打敌人3...... 重复此步骤直到弄死敌人为止。只剩最后一个敌人时可以让所有人都去打他。这样我们的回合数就是$\lceil \frac{\sum\nolimits_{i=1}^n{hp}_{i}}{n} \rceil$ 对于$k_1 ... k_n$,使用差分构造。将$k$排序后，令第$1$组的士兵数量为$k_1$,第$i$组$(i\neq1)$士兵数量为$k_i-k_{i-1}$即可。 ```cpp #include <bits/stdc++.h> using namespace std; int n,m,hp[1000005],num[1000005]; int main () { scanf("%d%d",&n,&m); for (int i = 1;i <= m;i++) scanf("%d",&hp[i]); vector<int> last = {0,n}; int sum = 0; for (int i = 1;i < m;i++) { sum += hp[i]; last.push_back(sum % n); } sort(last.begin(),last.end()); vector<int> sizes; for (int i = 1;i < last.size();i++) sizes.push_back(last[i] - last[i - 1]); printf("%d\n",(sum + hp[m] + n - 1) / n); for (int i = 0;i < sizes.size();i++) printf("%d ",sizes[i]); puts(""); int ptr = 0; for (int i = 1;i <= m;i++) { while (hp[i] > 0) { hp[i] -= sizes[ptr++]; printf("%d ",i); if (ptr == m) { ptr = 0;puts(""); } } } while (ptr && ptr++ != m) printf("%d ",m); return 0; } ``` 对着Rank2的代码写的