脚本宝典收集整理的这篇文章主要介绍了#贪心，构造#AT2266 [AGC008D] K-th K，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目

给你一个长度为 (N) 的整数序列 (X)，请判断是否存在一个满足下列条件的整数序列 (a)，如果存在，请构造一种方案

条件如下：

(a) 的长度为 (N^2)，并且满足数字 (1,2,3...N) 都各出现恰好 (N) 次

对于 (1leq ileq N)，数字 (i) 在 (a) 中第 (i) 次出现的位置是 (X_i)

分析

按照 (X) 从小到大排序，将 (1sim i-1) 的数直接找空位填，倒过来再做一次就可以了

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=501; int ans[N*N],n;
struct rec{int x,rk;}a[N];
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
inline void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48); 
}
bool cmp(rec x,rec y){return x.x<y.x;}
signed main(){
	n=iut();
	for (rr int i=1;i<=n;++i) a[i]=(rec){iut(),i};
	sort(a+1,a+1+n,cmp);
	for (rr int i=1;i<=n;++i){
		ans[a[i].x]=a[i].rk;
		rr int now=1;
		for (rr int j=1;j<a[i].rk;++j){
			for (;ans[now];++now);
			if (now>a[i].x) return !printf("No");
			ans[now]=a[i].rk;
		}
	}
	for (rr int i=n;i;--i){
		rr int now=n*n;
		for (rr int j=1;j<=n-a[i].rk;++j){
			for (;ans[now];--now);
			if (now<a[i].x) return !printf("No");
			ans[now]=a[i].rk; 
		}
	}
	printf("Yesn");
	for (rr int i=1;i<=n*n;++i) print(ans[i]),putchar(32);
	return 0;
}

​

脚本宝典总结

以上是脚本宝典为你收集整理的#贪心，构造#AT2266 [AGC008D] K-th K全部内容，希望文章能够帮你解决#贪心，构造#AT2266 [AGC008D] K-th K所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。