题解 CF1119G 【Get Ready for the Battle】

2019-06-01 09:46:12


搬运一下CF官方题解

最好的情况是除最后一次外都不浪费士兵,因此次数为 $\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}$ 即可。

#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的代码写的