> #include<cstdio>  
> #include<algorithm>  
> #include<cstring>  
> using namespace std;  
> const int L=1000005,inf=0x3f3f3f3f;  
> bool ck[L];  
> struct Line  
> {  
>     int left,right,val;  
> }line[L*4];  
> void build(int now,int left,int right)  
> {  
>     line[now].left=left;  
>     line[now].right=right;  
>     line[now].val=inf;  
>     if(left==right)return;  
>     build(now*2,left,(left+right)>>1);  
>     build(now*2+1,(left+right)/2+1,right);  
> }  
> void updata(int now,int pos,int val)  
> {  
>     int ll=line[now].left,rr=line[now].right,mid;  
>     if(ll==pos&&rr==pos)  
>     {  
>         line[now].val=min(line[now].val,val);  
>         return;  
>     }  
>     mid=(ll+rr)>>1;  
>     if(pos<=mid)  
>         updata(now*2,pos,val);  
>     else  
>         updata(now*2+1,pos,val);  
>     line[now].val=min(line[now*2].val,line[now*2+1].val);  
> }  
> int getmin(int now,int left,int right)  
> {  
>     int ll=line[now].left,rr=line[now].right,mid;  
>     if(ll==left&&rr==right)  
>         return line[now].val;  
>     mid=(ll+rr)>>1;  
>     if(right<=mid)  
>         return getmin(now*2,left,right);  
>     else if(left>mid)  
>         return getmin(now*2+1,left,right);  
>     else  
>         return min(getmin(now*2,left,mid),getmin(now*2+1,mid+1,right));  
> }  
> int main()  
> {  
>     int n,len,a,b,ans;  
>     while(scanf("%d%d",&n,&len)!=EOF)  
>     {  
>         build(1,0,len/2);  
>         scanf("%d%d",&a,&b);  
>         memset(ck,true,sizeof(ck));  
>         for(int i=0,x,y;i<n;i++)  
>         {  
>             scanf("%d%d",&x,&y);  
>             memset(ck+x+1,false,(y-x-1)*sizeof(bool));  
>         }  
>         updata(1,0,0);  
>         for(int i=a*2;i<=len;i+=2)  
>         {  
>             if(ck[i])  
>             {  
>                 int x=i/2-b,y=i/2-a,tp;  
>                 x=max(0,x);  
>                 tp=getmin(1,x,y);  
>                 if(tp==inf)  
>                     tp--;  
>                 updata(1,i/2,tp+1);  
>             }  
>         }  
>         ans=getmin(1,len/2,len/2);  
>         printf("%d\n",ans<inf?ans:-1);  
>     }  
>     return 0;  
> }  

• Re:此题绝壁有问题~下面的ac程序对于数据 1 11 1 2 3 6竟然输出3~其实应该是-1 (17) 1500012857 2016-06-22 10:04:08