最近开的题都有些 atcoder,不过相比于看题解都看得一头雾水的 ARC127E,这题反而更加良心。

已经想到了构造可行解的方法，但没有抽象出判断可行解的条件。看来卡在比较弱智的地方确实是个比较常见的事情。希望某天可以踢出这临门一脚。

说到底还是在这方面没什么脑子（

题意：请构造序列 ，满足元素 () 在该序列中恰好出现 次，且任意连续 个元素都互不相同，或报告无解。有解则输出字典序最小的解。

。

首先考虑如何判断有无解，尝试设计一个贪心。

既然是贪心，那就先满足最紧的限制，即先考虑 较大的元素，那么有一个方法就是隔 个位置放一个。

然后容易想到对 序列每 个分一块，那么最先考虑的元素当然是放在每一块的起始位置。设块数为 ，最后一块长度为 （因为最后一块长度最小）。

那么显然 ，且 。（就是这一步没有抽象出来）。

构造的方法是简单的，按 从大到小考虑每个元素，然后每次选择空位最多的段插进去即可。

然后基于此设计贪心使得字典序最小。

然后可以猜出一个贪心，即每次找到前 个位置中未出现的最小的元素，如果此时 ，那就只能选 的元素，然后处理后面长度 的子问题。

证明正确性，我们就是要证明，只要初始序列有解，每个时刻就都能选一个数出来。

反证法，考察第一个不合法的时刻。

1. 如果 ，因为无数可选，所以 的所有数都在前面 个位置出现过，而如果将前面 个数加入进来重新分块，那么此时 ，但仍然有 个 的数，那么会有 ，但在合法条件下，这个策略肯定不会让这种事发生，故矛盾。
2. 如果 ，此时选数没有限制，无数可选只可能是因为 的数只有至多 个，设当前位置加上后面有 个空位，如果 ，那么显然后面无解，而 保证了后面有解，故矛盾。所以 ，那么此时 ，所有的 都会等于 ，所以 ，矛盾。

综上所述，上述贪心一定可以构造出解，时间复杂度 。

#include <bits/stdc++.h>

using namespace std;
const int N = 5e2 + 5,M = 2e5 + 5;
inline int Knum(int n,int k) { return (n + k - 1) / k;}
inline int Klst(int n,int k) { return n % k == 0 ? k : n % k;}
int n,k,len;
int a[N];
int ans[M];
int ton[N];
int main()
{
	cin >> n >> k;
	for(int i = 1;i <= n;i++) cin >> a[i],len += a[i];
	int num = 0;
	for(int i = 1;i <= n;i++)
	{
		if(a[i] > Knum(len,k)) return puts("-1"),0;
		num += (a[i] == Knum(len,k));
	}
	if(num > Klst(len,k)) return puts("-1"),0;
	for(int i = 1;i <= len;i++)
	{
		memset(ton,0,sizeof ton);
		for(int j = max(1,i - k + 1);j < i;j++) ton[ans[j]] = true;
		num = 0;
		for(int j = 1;j <= n;j++) num += (a[j] == Knum(len - i + 1,k));
		for(int j = 1;j <= n;j++)
			if(!ton[j] && ((num < Klst(len - i + 1,k) && a[j])|| (num == Klst(len - i + 1,k) && a[j] == Knum(len - i + 1,k))))
			{
				ans[i] = j;
				--a[j];
				break;
			}
	}
	for(int i = 1;i <= len;i++)
		cout << ans[i] << ' ';
	return 0;
}