题目
点这里看题目。
分析
3100 的构造题，已经很奇妙了......
题目要求我们先输出所需的最少轮数。这一部分其实具有一定的提示性，因为我们可以猜一个下界，然后看是否能够达到它。比如，一个很好猜的下界就是 \(t_{\min}=\lceil\frac{\sum hp}{n}\rceil\)。
但事实是，如果没有很好的构造技巧，即使知道这个下界可以被构造出来也没有用。
我们可以先对这个下界进行一些简单的分析。我们称给令敌方总血量减少 \(n\) 的一步为“完美”的一步。如果要达到这个下界，就说明我们在前 \(t_{\min}-1\) 步中，每一步都必须是“完美”的。当 \(n\le m\) 的时候，这个要求很简单，我们只需要将每个组的大小都设置为 1 即可。
考虑 \(n>m\) 的时候。我们不妨再进行一些限制，例如我们要顺序攻击每一组敌军，并且要求在攻击前 \(m-1\) 组时，每一步都是“完美”的。此时，我们可以将前 \(m\) 组合并为一整组。那么前 \(m-1\) 组的每一条组间分界线必须和我方的某一条攻击组分界线重合。
也即，设 \(s_i=\sum_{k=1}^ihp_k\)，则对于所有的 \(1\le i<m\)，我们的构造攻击方案都满足存在一个攻击的前缀，它带来的伤害之和为 \(s_i\)。由于每一轮攻击伤害之和都是 \(n\)，因此我们构造的分组方案中，需要存在一个和为 \(s_i\bmod n\) 的前缀。
注意到需要满足的前缀只有 \(m-1\) 个，因此我们可以对 \(s_i\bmod n\) 排序后，取它们的差分，将剩下的再单独分成一组。最后扫描敌军的血量并分配即可。
小结：
-
在有步数限制的构造中，猜一个下界、上界可以让我们构造的目标清晰很多，也可以明确方向，降低构造难度。
-
注重基础分析，转换观察的角度。如果想不到“前面很多步都必须是‘完美’的”这个基础结论，那么后面的问题就很困难。同时，如果没有将若干组合并成为一组来观察，那也不简单了。
代码
#include <cstdio>
#include <algorithm>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
const int MAXN = 1e6 + 5;
template<typename _T>
void read( _T &x ) {
x = 0; char s = getchar(); bool f = false;
while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
if( f ) x = -x;
}
template<typename _T>
void write( _T x ) {
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + '0' );
}
template<typename _T>
_T MIN( const _T a, const _T b ) {
return a < b ? a : b;
}
int hp[MAXN];
int N, M;
namespace SmallN {
int seq[MAXN], tot;
void Solve() {
rep( i, 1, N ) putchar( '1' ), putchar( ' ' );
rep( i, N + 1, M ) putchar( '0' ), putchar( ' ' );
puts( "" );
rep( i, 1, M ) {
int tims = hp[i] / N;
rep( j, 1, tims ) {
rep( k, 1, M )
write( i ), putchar( ' ' );
puts( "" );
}
hp[i] %= N;
rep( j, 1, hp[i] )
seq[++ tot] = i;
}
for( int i = 1 ; i <= tot ; i += N ) {
int lim = MIN( N, tot - i + 1 );
rep( j, 1, lim ) write( seq[i + j - 1] ), putchar( ' ' );
rep( j, lim + 1, M ) putchar( '1' ), putchar( ' ' );
puts( "" );
}
}
}
namespace LargeN {
int pref[MAXN], val[MAXN], tmp[MAXN], pos[MAXN], tot;
void Solve() {
rep( i, 1, M ) pref[i] = pref[i - 1] + hp[i];
rep( i, 1, M - 1 ) tmp[++ tot] = pref[i] % N;
std :: sort( tmp + 1, tmp + 1 + tot );
tot = std :: unique( tmp + 1, tmp + 1 + tot ) - tmp - 1;
rep( i, 1, tot ) {
val[i] = tmp[i] - tmp[i - 1];
pos[tmp[i]] = i;
}
val[tot + 1] = N - tmp[tot];
rep( i, 1, M ) write( val[i] ), putchar( i == M ? '\n' : ' ' );
for( int i = 1, j ; i < M ; ) {
for( ; i < M && ! hp[i] ; i ++ );
if( i == M ) break;
int su = 0, lst = 0;
for( j = i ; j < M && ( su += hp[j] ) <= N ; j ++ );
for( int k = i ; k <= j ; k ++ ) {
while( lst < M && hp[k] >= val[lst + 1] ) {
hp[k] -= val[++ lst];
write( k ), putchar( ' ' );
}
if( lst == M ) break;
}
for( int i = lst + 1 ; i <= M ; i ++ )
hp[M] -= val[i], write( M ), putchar( ' ' );
puts( "" );
}
if( hp[M] > 0 ) {
int tims = ( hp[M] + N - 1 ) / N;
rep( j, 1, tims ) {
rep( k, 1, M )
write( M ), putchar( ' ' );
puts( "" );
}
}
}
}
int main() {
int su = 0;
read( N ), read( M );
rep( i, 1, M ) read( hp[i] ), su += hp[i];
printf( "%d\n", ( su + N - 1 ) / N );
if( N <= M )
SmallN :: Solve();
else
LargeN :: Solve();
return 0;
}