CF1119G Get Ready for the Battle 题解

题意：

敌方有 $m$ 个军队，血量分别为 $\mathtt{hp}_1, \mathtt{hp}_2, \cdots, \mathtt{hp}_m$。你有 $n$ 个军队，你需要将它们分成 $m$ 个组，其中第 $i$ 组有 $s_i$ 个军队 $(0 \leq s_i \leq n\land \sum s_i = n)$。

对于每轮攻击，你可以对这 $m$ 个组中的每个组 $i$，指定一个 (唯一确定的) 敌人 $e = e(i)$，并对其进行攻击。攻击完毕后，$\mathtt{hp}’_e \gets \mathtt{hp}_e - s_i$。如果一轮攻击后 $\mathtt{hp}’_i \leq 0$，则认为敌人 $i$ 已经被打败。

求至少需要几轮攻击，才能打败敌方的所有军队。

输入格式:

第一行包含两个正整数 $n, m(1 \leq m \leq n \leq 10^6)$，表示我方军队数和敌方军队数。

第二行包含 $m$ 个正整数 $\mathtt{hp}_1, \mathtt{hp}_2, \cdots, \mathtt{hp}_n(\sum \mathtt{hp}_i \leq 10^6)$，分别表示敌方各个军队的血量。

输出格式：

第一行输出一个整数 $t$，表示最少攻击的轮数。

第二行输出 $m$ 个非负整数 $s_1, s_2, \cdots, s_m(\sum s_i = n)$，其中 $s_i$ 表示第 $i$ 组的军队数量。

接下来的 $t$ 行，每行输出 $m$ 个整数，描述一轮攻击：

对于每轮攻击，输出 $m$ 个整数 $a_1, a_2, \cdots, a_m(1 \leq a_i \leq m)$，其中 $a_i$ 表示在该轮第 $i$ 组攻击敌人 $a_i$。$a_i$ 可以相同，也可以对 $\mathtt{hp}_j < 0$ 的 $j$ 进行攻击。

注意到每一轮的实际伤害都不会超过 $n$ ，因此一个显然的下界为 $ \left\lfloor\frac{\sum \mathtt{hp}_i}{n}\right\rfloor$ 。

考虑构造一种方案以达到这个下界。

不妨设 $\sum_{1 \le i \le m} \mathtt{hp}_i \equiv 0 \pmod{n}$ ，否则就把 $\mathtt{hp}_m$ 变大，而这个操作不会改变下界的值。

考虑合理分配伤害，使得 $\mathtt{hp}_i$ 不至于减到负数。

则对于每个 $\mathtt{hp}_i$ ，一定存在一组对应的 $\sum s \equiv \mathtt{hp}_i \pmod{n}$ 。

不妨设我们是依次消灭每个敌人的，则最优的方案一定满足：

$\sum_{1 \le j \le i} \mathtt{hp}_j \equiv \sum_{1\le j \le l_i} s_j \pmod{n}$

因为对于 $\mathtt{hp}_1$ ，设我们用了前 $l_1$ 个 $s$ ，则

$\mathtt{hp}_1 = U_1 \times n + \sum_{1 \le i \le l_1} s_i$

对于 $\mathtt{hp}_2$ ，设我们用了 $(l_1,l_2]$ 的 $s$ 去打，则

$\mathtt{hp}_1 + \mathtt{hp}_2 = (U_1+U_2) \times n + \sum_{1 \le i \le l_2} s_i$

以此类推，可知

$\sum_{1 \le i \le m} \mathtt{hp}_i = \left(\sum U_i\right)\times n + \sum_{1 \le i \le (l_m=m)} s_i$

构造方法很简单，把 $\mathtt{hp_i}$ 的前缀和 $S_i = \sum_{1 \le j \le i} \mathtt{hp}_j$ 按模 $n$ 的值排序，然后它的差分数组就是 $s$ 。

为啥呢，其实就相当于有 $m-1$ 个条件，形如 $s$ 的某个前缀和为多少。~~第 $m$ 个即 $\sum s = n$ ，显然满足~~。

时间复杂度 $\mathcal{O}\left(\frac{m}{n} \sum \mathtt{hp_i}\right)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e6+15))

int n,m,sum,cnt,a[N],b[N],c[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=0; i<m; i++) { cin >> a[i]; b[i] = (sum += a[i]) % n; }
    cout << (sum + n - 1) / n << '\n';
    b[m-1] = n; sort(b, b+m); c[0] = b[0]; for(int i=1; i<m; i++) c[i] = b[i] - b[i-1];
    for(int i=0; i<m; i++) cout << c[i] << " \n"[i==m-1];
    for(int i=0, j=0; i<m; i++) for(; a[i] > 0; a[i] -= c[j], (++j) %= m) b[cnt++] = i;
    for(int i=0; i<cnt || i % m; i++) cout << ++b[i] << " \n"[(i + 1) % m == 0];
    return 0;
}