剩下50%的數據 1?≤?n?≤?5000, 1?≤?ki?≤?5000。

思路:首先對于每個科學家我們知道他們k個問題的相對順序不能改變,所以對于每個科學家來說他們問題本身的順序就有可能存在壞對,由于題目中所說對于同一個科學家的問題,只要求相對順序不變,他們可以拆開插到別的科學家的問題之間.那么我們就可以設想,我們先分別記錄每個科學家本身問題順序的壞對的最大值,那么這個最大值是否可以作為問題的最后結果呢？答案是可以的，就按照以上提到的,我們可以將其余科學家的問題按照大小順序穿插在那個本身壞對數最大的科學家的問題之中而不產生新的壞對數.我們可以對這些問題進行分層,對于每個科學家第一次出現壞對時（如果沒有壞對就是整個序列）然后進行歸并排序.（這里也可以選擇其他穩定的排序方法,因為每個問題的相對順序不能改變 所以只能選擇穩定的排序）一直到第sum層。。。

證明：首先對于每一個科學家自身的序列來說，由于我們用的是歸并排序，所以絕對不會改變每一個科學家自身序列的相對順序。其次對于每一層的序列，我們經過排序后肯定是保證嚴格遞增的（即不存在壞對），對于下一層的序列來說同樣如此，由于下一層的序列的問題中和上一層的序列的問題中至少存在著一個壞對，所以對于下一層的第一個數（也是最小的那個數）必定是小于上一層的最后一個數的，也就是說保證了2層之間有一個壞對數。那么最終答案就是sum個壞對數，也就是最少的壞對數。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define ll long long#define N 200010using namespace std;struct tc{	int cnt,count;//cnt下標 count 問題數量	ll p[5001];}q[5001];struct sc{	int id;//下標	ll num;//消耗}anss[N],s[N];void merge(int l,int mid,int r)//歸并排序{	int i=l,j=mid+1;	int cc=l;	while(i<=mid&&j<=r)	{		if(anss[i].num<=anss[j].num)		{			s[cc].id=anss[i].id;			s[cc++].num=anss[i++].num; 		}		else		{			s[cc].id=anss[j].id;			s[cc++].num=anss[j++].num; 		}	}	while(i<=mid)	{			s[cc].id=anss[i].id;			s[cc++].num=anss[i++].num; 	}	while(j<=r)	{			s[cc].id=anss[j].id;			s[cc++].num=anss[j++].num; 	}	for(i=l;i<cc;i++)	{			anss[i].id=s[i].id;			anss[i].num=s[i].num;	}		return ;}void mergesort(int x,int y){	if(x<y)	{		int mid=(x+y)/2;		mergesort(x,mid);		mergesort(mid+1,y);		merge(x,mid,y); 	}	return ;}int main(){	int i,j;	ll n,a,x,y,m;	int ans=-1,k,sum,l=0;	cin>>n;	for(i=0;i<n;i++)	{		scanf("%d %I64d %I64d %I64d %I64d",&k,&a,&x,&y,&m);		sum=0;		l+=k;		q[i].cnt=1;		q[i].count=k;		q[i].p[1]=a; 		for(j=2;j<=k;j++)		{			q[i].p[j]=(x*q[i].p[j-1]+y)%m;			if(q[i].p[j]<q[i].p[j-1])			sum++;		}		ans=max(ans,sum);//找最大	}	PRintf("%d/n",ans);	int st=0,end=0;	while(end<l)	{		for(i=0;i<n;i++)//分層歸并排序		{			for(j=q[i].cnt;j<=q[i].count;j++)			{				if(j!=q[i].cnt&&q[i].p[j]<q[i].p[j-1])// 每一層的第一個j 不能和前一個比較				{ q[i].cnt=j;				  break;				}				anss[end].id=i;				anss[end++].num=q[i].p[j];			}			if(j>q[i].count)//如果沒有壞對就是整個序列			q[i].cnt=j;		}		mergesort(st,end-1);		st=end;	}	for(i=0;i<l;i++)	printf("%I64d %d/n",anss[i].num,anss[i].id+1);	return 0;}
下面說一下對于這道題一個非常巧妙的方法,把兩個方法放在一起.兩個問題的思想完全一樣 都是進行分層排序,我們上一個是采用的分層歸并排序,這里思想非常巧妙?。?！
利用結構體并且+快排直接分層排序
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define ll long longusing namespace std;ll n,a,k,x,y,m,b;struct node{	int x,y,z;//x 表示層數 y 表示的是所需資源單位數  z表示的是科學家的編號}p[200010];int cmp(node w,node l)//這里非常巧妙！如果層數相等 在同一層里我們就按照所需資源單位數排序,如果資源單位數相同就按照科學家
//編號排序,否則就按照層數排序{	if(w.x==l.x)		return w.y<l.y||(w.y==l.y&&w.z<l.z);	return w.x<l.x; }int main(){	int i,j;	int ans=-1,cnt=0;	cin>>n;	for(i=1;i<=n;i++)	{		int t=0;//t 計算為第幾層,這里都一樣我們還是按照壞對來分層出現一次為一層,沒有壞對就是整個序列		scanf("%I64d %I64d %I64d %I64d %I64d",&k,&a,&x,&y,&m);			for(j=1;j<=k;j++)//這里是分層的關鍵！		{				p[cnt++]=(node){t,a,i};				b=(x*a+y)%m;				if(b<a&&j!=k)//第k個問題沒有最后一個b				t++;				a=b;		}		ans=max(ans,t);	}	printf("%d/n",ans);	sort(p,p+cnt,cmp);	for(i=0;i<cnt;i++)	{		printf("%d %d/n",p[i].y,p[i].z);	}	return 0;}