CF1765H题解

思路：对每个病人单独来考虑。我们发现正着来考虑每个位置放哪个病人不能保证对之后的病人无影响，故尝试着反着做，当前处理到第 \(i\) 个位置时，第 \(t\) 个还没有被放置的病人能放置仅当 \(p_t \ge i\) 并且所有必须在他之前被放置的病人已经被放置，显然病人 \(t\) 在 \(i\) 前面的位置也一定可以放，所以我们只需要用数据结构来维护能够放置的病人的集合，同时随便拿一个出来放，当集合为空时就是能放的最前面的位置。

正确性：将 \(m\) 个约束条件看做有向边，最终会形成一张拓扑图（因为保证一定有解），所以我们实际在做拓扑排序。

code:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define mp(a,b) make_pair(a,b)
using namespace std;
const int N=2010;
typedef pair<int,int>pii;
int n,m,p[N],din[N];
vector<int>v[N];
void work(int k)
{
	priority_queue<pii>q;
	memset(din,0,sizeof(din));
	rep(i,1,n)
		rep(j,1,v[i].size())din[v[i][j-1]]++;
	rep(i,1,n)if(i!=k&&!din[i])q.push(mp(p[i],i));
	per(i,n,1)
	{
		if(q.empty()||q.top().first<i){printf("%d ",i);return;}
		int x=q.top().second;q.pop();
		rep(j,1,v[x].size())
			if(!--din[v[x][j-1]]&&v[x][j-1]!=k)q.push(mp(p[v[x][j-1]],v[x][j-1]));
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	rep(i,1,n)scanf("%d",&p[i]);
	rep(i,1,m)
	{
		int x,y;scanf("%d%d",&x,&y);
		v[y].push_back(x);
	}
	rep(i,1,n)work(i);
	return 0;
}