行，表示解决问题的最优顺序。每一行两个用空格隔开的整数，表示这个问题所需的资源单位数和提供这个问题的科学家的编号。样例输入22 1 1 1 102 3 1 1 10样例输出01 12 13 24 2数据规模和约定 20%的数据 n = 2, 1 ≤ ki ≤ 2000； 另外30%的数据 n = 2, 1 ≤ ki ≤ 200000；剩下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;}
新闻热点
疑难解答
