A.[
题意
每个manager给数组a的第1到r[i]个数排序,t[i]==1则排升序,2则排降序。求m个manager排序完的序列。
分析
如果之前的r比较小,肯定会被更大的r的操作覆盖掉,所以我们要找到r的递减序列。
先找出最大的r,然后在这个r的后面再找最大的r,循环这样,找出了一个r的递减的序列,然后再模拟排序。但是最坏情况:【r刚好从最大到最小,这样每次都要排一下序】时间复杂度mlogm+m*nlogn,会超时。
改成填数复杂度就变成mlogm+n,填数就是先给a的最大的r之前的数排个序,最大的r到第二大之间,如果是升序,那就把a大的那一头填进去,如果是降序,就把小的那一头填进去。以此类推前面的区间。
不过我找r的递减序列时出错了:只要id大于刚刚的manager的id(出现得更迟),并且排序方法不一样就让这个manager排一下。
int j=1; solve(j);//第j个(按r排)manager来排a for(int i=2; i<=m; i++) { if(b[i].id>b[j].id&&b[i].t!=b[j].t) { solve(i); j=i; } }
wa在test 14,但是因为太长,没法看到完整的数据,所以自己造数据,终于找出错在哪了,一个反例:
9 3 1 2 3 4 5 6 7 8 9 2 9 1 4 2 6
n=9,m=3
r:9 4 6 t:2 1 2 我的程序会先排9,升序,然后因为6升序,所以不排,于是j没有更新为6,然后排4,降序,这样就错了,因为4其实在6之前出现,所以应该忽略。 循环里改为这样就好了:if(b[i].id>b[k].id) { if(b[i].t!=b[j].t) { r[cnt++]=i; j=i; } k=i; }
k就是上一个排序的id,如果现在这个id大,就是后面的manager,现在的排法和前一个记录在r序列里的不一样,就记录进去。
代码
#include#include #define N 200005 using namespace std; int n,m,a[N],c[N],r[N]; struct mng { int r,t,id; } b[N]; int cmp(mng a,mng b) { return a.r>b.r; } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) scanf("%d",&a[i]); for(int i=1; i<=m; i++) { scanf("%d%d",&b[i].t,&b[i].r); b[i].id=i; } sort(b+1,b+1+m,cmp);//manager按r排降序 int j=0,k=0,cnt=0; //筛选出r递减的manager序列 for(int i=1; i<=m; i++) { if(b[i].id>b[k].id) { if(b[i].t!=b[j].t) { r[cnt++]=i; j=i; } k=i; } } for(int i=b[1].r+1; i<=n; i++) c[i]=a[i]; sort(a+1,a+1+b[1].r);//a数组b[1].r前的排升序 int tou=1,wei=b[1].r; for(int i=0; i b[r[i+1]].r; j--) //小的从右到左放过去 c[j]=a[tou++]; else for(int j=b[r[i]].r; j>b[r[i+1]].r; j--) c[j]=a[wei--];//大的从右到左放过去 for(int i=1; i<=n; i++) printf("%d ",c[i]); return 0; }
B.没看