首页 > 代码库 > NYOJ 631 冬季长跑

NYOJ 631 冬季长跑

冬季长跑

时间限制:5000 ms  |  内存限制:65535 KB
难度:4
描述

为了增强大学生的身体素质,校长决定进行冬季长跑。有N个班级要参加冬季长跑,班级的编号从1到N。听说这个消息之后学生们马上都集中到体育场上。但是,由于学生们来的匆忙,所以并不是按照学号排列的。这样很混乱,所以要让他们调整位置按学号排列。为了防止调整过程出现混乱,校长要求,每个班级每次只能找相邻的两个人交换位置。我们认为每次交换都需要花费10秒时间。当然,每个班级都会采取最快的方案交换完毕,在整理好队列后就立即出发。由于每个班级要整理队列的时间不同,所以校长决定要将长跑的N个班级分成若干小组,每个小组中的班级利用一条跑道。在每个跑道上的班级必须满足,前面的班级的编号小于后面的班级的编号。在调整队列之前,我们的校长想知道,最少需要用到多少条跑道。

注意:同时出发的两个班级不可以在同一条跑道上。 

样例Hint

说明:班级1、2、3调整所需时间分别为0s、30s、10s,所以至少需要两条跑道,有两种可能:1、2共用一条跑道,3单独一条;或者1、3共用一条跑道,2单独一条。 

输入
一个整数T表示测试组数。

对于每组测试数据:

首先、一个整数N代表班级的个数。

然后、后面有N行,每行代表一个班级。每行由一个整数Mi和后面的Mi个整数。其中Mi是班级i的人数,后面的Mi是未排队之前的班级i的学号队列,范围1~Mi。
输出
对于每组数据,输出一个整数K,代表最少的跑道数。每组输出各占一行。


数据范围:
1 <= T <= 10
1 <= N <= 50000
1 <= Mi<= 20
样例输入
1
3
3 1 2 3
3 3 2 1
3 2 1 3 
样例输出
2
树状数组求逆序数+单调递增子序列!
当然也可以用归并排序求逆序数!
本题应用树状数组求逆序数的好处:因为是学生学号,学号比连续,因此不需要考虑离散化,也不需要考虑去重!
AC码:
#include<stdio.h>
#include<string.h>
int num[25],m;
int sum[50005];
int lowbit(int i)
{
	return i&(-i);
}
void update(int i)
{
	while(i<=m)
	{
		num[i]+=1;
		i+=lowbit(i);
	}
}
int get(int i)
{
	int result=0;
	while(i>0)
	{
		result+=num[i];
		i-=lowbit(i);
	}
	return result;
}
int main()
{
	int T,n,i,j,a,ans,k,count;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		memset(sum,0,sizeof(sum));
		for(i=0;i<n;i++)
		{
			scanf("%d",&m);
			ans=0;
			memset(num,0,sizeof(num));
			for(j=1;j<=m;j++)
			{
				scanf("%d",&a);// 学号无重复
				update(a);
				ans+=j-get(a); //树状数组求逆序数
			}
		//	printf("%d\n",ans);  // ans为逆序数
			sum[i]=ans*10;
		}

		// 求单调递增子序列的个数
		count=0;
		for(i=0;i<n;i++)
		{
			if(sum[i]!=-1)
			{
				k=sum[i];
				sum[i]=-1;
				for(j=i+1;j<n;j++)
				{
					if(sum[j]!=-1&&sum[j]>k)
					{
						k=sum[j];
						sum[j]=-1;
					}
				}
				count++;
			}
		}
		printf("%d\n",count);
	}
	return 0;
}