M. My University Is Better Than Yours(思维)

Problem - M - Codeforces

题意:

题意：给定m个含有n个元素的排列，规定元素x大于y的话只需要有一个排列中有x在y前面即可。而x大于z的话又可以通过这样的步骤来得出：
1.x在某个排列里比y靠前
2.y在某个排列里比z靠前
3.所以x比z大

输出m个数，每个数代表第i个元素比多少元素大。

第一行包含两个整数n和m（1≤n≤5×105，1≤m≤5×105，1≤n×m≤106），表示考虑的大学数量，和大学排名的数量。

然后是m行。第i行包含n个不同的整数si,1, si,2, ..., si,n（1≤si,j≤n），表示第i个大学排名的顺序（从高到低）。

输出
输出一行n个整数a1,a2,...,an，用空格分隔。第i个数字ai表示第i所大学优于的大学数量。'

题解:

突破点就是每一行都是一个排列，我们知道一个排列中每个元素仅出现一次，那么我们按照列优先去遍历他给出的n列m行矩阵。

如果遍历到的矩阵的元素是第一次出现，那么我们要记录这个数，同时记录到目前为止有多少个“第一次出现”的数。

假如第一列有两个第一次出现的数是1和2，如果我们想说1和2比剩下的所有数(n-1个数)都大，那么我们就应该确保第一列和第二列不会再出现“第一次出现的数”。否则，如果第二列出现了新的“第一次出现”的数3，那么势必代表在这个3出现的哪一行里1和2中有一个跑到了第二列的3的后面，那么就可以论证3大于1也大于2。所以3就也比剩下的所有数都大。然后就继续要去遍历前三列没有新增的第一次出现的数。

具体见代码

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int> a[500050];
int vis[500050];
int ans[500050];
int main()
{
	int n,m;
	cin >> n >> m;
	for(int i = 1; i <= m;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			int x;
			cin >> x;
			a[i].push_back(x);
		}
	}
	int num = 0;
	queue<int> q;
	for(int i = 0,las = 1;i < n;i++)
	{
		for(int j = 1;j <= m;j++)
		{
			if(!vis[a[j][i]])
			{
				vis[a[j][i]] = 1;
				num++;
				q.push(a[j][i]);
			}
		}
		if(num == i+1)
		{
			while(q.size())
			{
				int k = q.front();
				q.pop();
				ans[k] = n - las;
			}
			las = num + 1;
		}
	}
	for(int i = 1;i <= n;i++)
	{
		cout<<ans[i]<<" ";
	}
}