agc008_d

点击打开链接

题意

给出数组 (A_1,A_2cdots A_n) 。

求一个长度为 (n) 的数组使得：

• (1sim n) 中的每个数恰好出现 (n) 次
• 对于任意 (1le ile n) ，(i) 在序列中第 (i) 次出现的位置为 (A_i)

题解

其实一个限制可以拆成两个：

• 第 (A_i) 位为 (i)
• 前 (A_i-1) 位有恰好 (i-1) 个 (i)

那么直接贪心构造即可。

具体的，(A_i) 越小越先满足 (i) 的条件。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int NN = 505, NLEN = 500 * 500 + 5;
int A[NN], N, ans[NLEN], id[NN];
bool cmp(int u, int v) { return A[u] < A[v]; }
int main() {
	freopen("kth.in", "r", stdin);
	freopen("kth.out", "w", stdout);
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) {
		scanf("%d", &A[i]);
		ans[A[i]] = i;
		id[i] = i;
	}
	sort(id + 1, id + N + 1, cmp);
	//这需要给 A[i]排序
	int p = 1;
	for (int i = 1; i <= N; ++i) {
		int cnt = 0;
		for (int j = 1; j < A[id[i]]; ++j) {
			if (ans[j] == 0) {
				if (cnt == id[i] - 1)
					break ;
				++cnt;
				ans[j] = id[i];
			}
		}
		if (cnt < id[i] - 1) {
			printf("No
");
			return 0;
		}
	}
	for (int i = 1; i <= N; ++i) {
		int cnt = 0;
		for (int j = A[id[i]] + 1; j <= N * N; ++j) {
			if (cnt == N - id[i])
				break ; //这句话得放在前面，不能放在后面
			if (!ans[j]) {
				ans[j] = id[i];
				++cnt;
			}
		}
		if (cnt != N - id[i]) { //记得判这个
			printf("No
");
			return 0;
		}
	}
	printf("Yes
");
	for (int i = 1; i <= N * N; ++i)
		printf("%d ", ans[i]);
	printf("
");
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
4
3 4 16 9
*/