做了一夜 再也不想敲键盘了..等等再报告 贴出来先 (其实又没人看….)
没有什么任何优化 直接0msAC 真不好意思 XD
#include <cstdio>
#include <cstring>
#include <cmath>
#define MAXNUM 2000
typedef struct pair {
int v,l;
} Pair;
typedef struct pointer {
int p,num;
} Pointer;
Pair a[MAXNUM],r[MAXNUM];
int width,prow,rp;
Pointer p2,p5,p8;
void calc();
void set(Pointer *target,int p,int num);
void go(int spit,int steps);
void gop(Pointer *p,int steps);
int pre(Pointer p);
int next(Pointer p);
int spit();;
int main() {
int i;
while(1) {
rp=0;
scanf("%d",&width);
if(width==0) {
printf("0\n");
return 0;
}
for(i=1;;i++) {
scanf("%d%d",&a[i].v,&a[i].l);
if(!a[i].v&&!a[i].l)
break;
}
a[0].v=a[i].v=-1;
a[0].l=a[i].l=width;
r[0].v=-1;
r[1].l=0;
calc();
printf("%d\n",width);
for(i=1;;i++) {
printf("%d %d\n",r[i].v,r[i].l);
if(!r[i].v&&!r[i].l)
break;
}
}
}
void calc() {
int i,counter;
int x,y,z,steps;
prow=1;
set(&p2,0,1);
set(&p5,1,1);
counter=0;
for(i=1;counter<=width;i++)
counter+=a[i].l;
i--;
set(&p8,i,width-counter+a[i].l+1);
while(1) {
if(a[p5.p].v==-1)
break;
x=a[p2.p].l-p2.num;
y=a[p5.p].l-p5.num;
z=a[p8.p].l-p8.num;
steps=x>y?y:x;
steps=steps>z?z:steps;
if(steps<3) {
go(spit(),1);
continue;
} //可在此处插入判断边界程序
go(spit(),1);
go(spit(),steps-1);
}
rp++;
r[rp].v=r[rp].l=0;
}
void set(Pointer *target,int p,int num) {
target->p=p;
target->num=num;
}
int spit(){
int result=0,i=0,temp,x=a[p5.p].v;
bool top=false,bottom=false;
if(a[p2.p].v==-1)
top=true;
if(a[p8.p].v==-1)
bottom=true;
if(prow!=1) {
if(!top)
result=(temp=fabs(pre(p2)-x))>result?temp:result;
result=(temp=fabs(pre(p5)-x))>result?temp:result;
if(!bottom)
result=(temp=fabs(pre(p8)-x))>result?temp:result;
}
if(prow!=width) {
if(!top)
result=(temp=fabs(next(p2)-x))>result?temp:result;
result=(temp=fabs(next(p5)-x))>result?temp:result;
if(!bottom)
result=(temp=fabs(next(p8)-x))>result?temp:result;
}
if(!top)
result=(temp=fabs(a[p2.p].v-x))>result?temp:result;
if(!bottom)
result=(temp=fabs(a[p8.p].v-x))>result?temp:result;
return result;
}
int pre(Pointer p) {
if(p.num==1)
return(a[p.p-1].v);
else
return(a[p.p].v);
}
int next(Pointer p) {
if(p.num==a[p.p].l)
return(a[p.p+1].v);
else
return(a[p.p].v);
}
void go(int spit,int steps) {
if(r[rp].v==spit)
r[rp].l+=steps;
else {
rp++;
r[rp].v=spit;
r[rp].l=steps;
}
gop(&p2,steps);
gop(&p5,steps);
gop(&p8,steps);
prow=(prow+steps-1)%width+1;
}
void gop(Pointer *p,int steps) {
p->num+=steps;
while(p->num>a[p->p].l) {
p->num-=a[p->p].l;
p->p++;
}
}
