CCF201403(2)经典窗口问题

一下午苦战窗口问题，我的天终于满分AC——20170318 90分...QAQ 实在想不出哪里没过，有可能测评系统对冗余代码没好感吧... 使用链表的方法，很快，但是我对于指针还是没有很熟，等明天考完再三站搞定指针链表法吧 采用模拟链表方法，使用数组很快，搞清楚data数组与right数组的关系以及当次序改变时的变换规则就很快了 #include<stdio.h> #include<stdlib.h> typedef struct node { int data; int x1,y1,x2,y2; }Ind; int main() { int wdata[11]={0}; int wright[11]={0}; int b[11][2]={0}; int ok[11]={0}; int m,n,i,j,dj,temp; scanf("%d%d",&n,&m); Ind wind[11]; for(i=1;i<=n;i++) { scanf("%d%d%d%d",&wind[i].x1,&wind[i].y1,&wind[i].x2,&wind[i].y2); wind[i].data=i; } for(j=1;j<=m;j++) scanf("%d%d",&b[j][0],&b[j][1]); for(i=n;i>=1;i--) wdata[n-i+1]=i; for(i=0;i<n;i++) wright[i]=i+1; for(i=1;i<=m;i++) //for(j=0;j<=n;j++) { j=0; //j=wright[j]; while(1) { //从顶层开始取矩形位置范围 temp=wright[j]; dj=wdata[temp]; if((b[i][0]>=wind[dj].x1)&&(b[i][0]<=wind[dj].x2)&&(b[i][1]<=wind[dj].y2)&&(b[i][1]>=wind[dj].y1)) { ok[i]=dj; //本次点击层数为 dj wright[j]=wright[temp]; wright[temp]=wright[0]; wright[0]=temp; break; //进行下次点击 } else { j=wright[j]; if(!j) break; } } } for(i=1;i<=m;i++) { if(ok[i]) printf("%d\n",ok[i]); else printf("IGNORED\n"); } return 0; } ------------------------------------------------------------------------------------------------------------------------------------------------- 华丽分界线，之前的代码交换窗口位置方法是不对的，90分都给多了系统爸爸QAQ #include<stdio.h> int changenum(int kk,int*a,int n); struct { int x1,y1,x2,y2; }a[11]; //结构体存储构建矩形的坐标 int main() { int n,m,i,j,dj; int b[11][2]={0}; //存储每次点击的位置坐标 int ok[10]={0}; //存储每次点击的层号 int book[11]={0}; //自顶向下标记当前状态的层号 scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2); for(j=1;j<=m;j++) scanf("%d%d",&b[j][0],&b[j][1]); for(i=1;i<=n;i++) book[i]=n+1-i; for(i=1;i<=m;i++) for(j=1;j<=n;j++) { dj=book[j]; //从顶层开始取矩形位置范围 if((b[i][0]>=a[dj].x1)&&(b[i][0]<=a[dj].x2)&&(b[i][1]<=a[dj].y2)&&(b[i][1]>=a[dj].y1)) { ok[i]=dj; //本次点击层数为 dj changenum(dj,book,n); //调整各层位置关系函数 j=n+1; //进行下次点击 } } for(i=1;i<=m;i++) { if(ok[i]) printf("%d\n",ok[i]); else printf("IGNORED\n"); } return 0; } int changenum(int kk,int*a,int n)//调整各层位置关系函数 { if(kk==n)//如果 本次点击 KK 层数为顶层 n 则无需调整 return 0; else { a++; //用指针依次自顶向下读取各层层号 *a=kk; a++; int k=n; while(k) { if(k!=kk)//跳过被点击到的 KK 层 { *a=k; a++; k--; } else k--; } } }