USACO2011December Silver A

题意：

​ 今天的奶牛们特别调皮！Farmer John 想做的只是给排成一排的奶牛拍照，但是在他拍下照片之前，奶牛们一直在移动。

具体地说，FJ 有 N 头奶牛 \(（1≤N≤20000）\)，每头奶牛都有一个唯一确定的编号。FJ 想要以一个特定的顺序拍下一张奶牛排成一排的照片，这个顺序用数组 \(A[1\dots N]\) 表示，其中 \(A[i]\) 代表排在 i 位置的奶牛的编号。

他按照这样的顺序将奶牛们排列好，但在他按下快门之前，有些奶牛（可能是零头或任意多头奶牛，位置也不一定连续）将移到一个新的位置。更准确地说，一些奶牛离开队列，剩下的奶牛靠拢，这些离开的奶牛再将自己重新插入到队列中的任意位置（不一定是他们之前的位置）。FJ 感到非常沮丧，他再次按照 \(A\) 数组的顺序重新安排了队列。但在他再次按下快门之前，又有一些奶牛移动到了新的位置。

就这样，FJ 拍了五张照片。给出每张照片拍摄的内容（即 FJ 按下快门时奶牛的顺序），请你尝试推算出 FJ 最初为奶牛们排的顺序（即 \(A\) 数组）。由于可能有奶牛移动，照片显示的顺序与原来的顺序可能有所不同。但是，一头奶牛最多只会移动一次：即如果一头奶牛在拍其中一张照片时移动了，它在拍其他四张照片的时候都不会移动。当然，由于其他奶牛也在移动，它在不同照片中的顺序并不一定相同。

---

​ 显然的一点，因为一头牛最多只会在一张照片中移动。假如我们现在有两头牛 \(A\),\(B\)，如果 \(A\) 在 \(B\) 的右边，当且仅当 \(A\) 在五张照片中起码有 3 次在 \(B\) 牛的右边。

​ 一个朴素的想法，如果 \(A\) 在 \(B\) 的左边，就连一条 \(A\) 到 \(B\) 的有向边。然后跑一遍拓扑排序就好了。时间复杂度是 \(O(n^2)\)，空间复杂度也是 \(n^2\)。这样能拿到 82 pts。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e4+5;
int n,a[6][MAXN],b[MAXN],nxt[6][MAXN];
int to[MAXN],cnt[MAXN],in[MAXN],pos[6][MAXN];
bool bef[MAXN];
vector <int> e[MAXN];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=5;++i)
		for(int j=1;j<=n;++j)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;++i)
		b[i]=a[1][i];
	sort(b+1,b+1+n);
	for(int i=1;i<=5;++i)
		for(int j=1;j<=n;++j)
		{
			a[i][j]=lower_bound(b+1,b+1+n,a[i][j])-b;
			pos[i][a[i][j]]=j;
		}
	for(int i=1;i<=n;++i)
	{
		memset(cnt,0,sizeof cnt);
		for(int k=1;k<=5;++k)
			for(int j=pos[k][i]+1;j<=n;++j)
				cnt[a[k][j]]++;
		for(int j=1;j<=n;++j)
		{
			if(cnt[a[1][j]]>=3)
			{
				e[i].push_back(a[1][j]);
				in[a[1][j]]++;
			}
		}
	}
	queue <int> q;
	for(int i=1;i<=n;++i)
		if(!in[i]) q.push(i);
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		printf("%d\n",b[now]);
		for(int i=0;i<e[now].size();++i)
		{
			int to=e[now][i];
			in[to]--;
			if(!in[to]) q.push(to);
		}
	}
	return 0;
}

​ 那么如何拿到满分呢。我们会发现，拓扑排序这种做法其实是做了很多无用功。有些边不需要连其实也能得出答案。我们连边实际上就是设立一种大小关系，如果 \(A\) 在 \(B\) 右边就说明 \(B>A\) 。我们用拓扑所做的不过就是用我们设立起来的大小关系进行排序罢了。那么我们为什么要用时间复杂度为 \(O(n^2)\) 的排序方法，而不用更快的，时间复杂度能达到 \(O(n\times \log(n))\) 的快排呢？所以，我们重新定义一个 cmp 比较函数，然后直接 sort 一遍就好了。cmp 函数的编写与上文的连边条件相同，记得离散化。详情见代码。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e4+5;
int n,a[6][MAXN],b[MAXN],pos[6][MAXN];
bool cmp(int x,int y)
{
	int cnt=0;
	for(int i=1;i<=5;++i)
		if(pos[i][x]<pos[i][y]) ++cnt;
	return cnt>=3;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=5;++i)
		for(int j=1;j<=n;++j)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;++i)
		b[i]=a[1][i];
	sort(b+1,b+1+n);
	for(int i=1;i<=5;++i)
		for(int j=1;j<=n;++j)
		{
			a[i][j]=lower_bound(b+1,b+1+n,a[i][j])-b;
			pos[i][a[i][j]]=j;
		}
	sort(a[1]+1,a[1]+1+n,cmp);
	for(int i=1;i<=n;++i)
		printf("%d\n",b[a[1][i]]);
	return 0;
}

​ 总结：我想到 \(O (n^2)\) 的拓扑排序。但是没注意到这趟拓扑排序的本质是排序。这种用 sort 的方法还是比较巧妙的。关注问题的本质还是十分重要的。