首页 > 代码库 > Countries

Countries

Countries

题目链接:http://hihocoder.com/problemset/problem/1391

预处理+双指针

      首先将A->B,B->A的导弹全部转化为B->A的导弹(因为不需要计算B承受的伤害,所以对于A->B的导弹,只需记录被B的防护罩返回来的导弹即可).

      然后对于每个导弹计算将其反弹回B,A所需要的最小的防护罩区间[l,r](这个操作在O(1)的时间完成,画张图就很好推了)

      于是问题就转化为了:

      数轴上有一些固定区间,每个固定区间都有一个权值,现在有一个长度为Ta的防护罩区间,问用这个防护罩区间完整包含的固定区间的权值和最大为多少?

      对于这个问题,可以将固定区间的左右两端点标号,存到一个数组(struct{int position,index,value;}),然后用一个vis数组标记第index个固定区间在防护罩区间内的情况,遍历一遍防护罩区间的L即可.

代码如下:

技术分享
  1 #include<cstdio>  2 #include<algorithm>  3 #include<cstring>  4 #define N 20005  5 #define R (L+Ta)  6 using namespace std;  7 typedef long long LL;  8 LL Ta,Tb,X,n,m,k,sum,pt;  9 bool vis[50005]; 10 struct point{ 11     LL times,index,v; 12 }p[50005]; 13 struct node{ 14     LL fire,fly,dam; 15     LL l,r; 16 }launch[N]; 17 bool cmp(point a,point b){ 18     return a.times<b.times; 19 } 20 void init(){ 21     sum=0; 22     memset(vis,0,sizeof(vis)); 23     memset(p,0,sizeof(p)); 24     memset(launch,0,sizeof(launch)); 25     scanf("%I64d",&X); 26     scanf("%I64d%I64d",&n,&m); 27     k=pt=0; 28     for(LL i=0;i<n;++i){ 29         LL a,b,c; 30         scanf("%I64d%I64d%I64d",&a,&b,&c); 31         if(X<=a+b&&a+b<=X+Tb){ 32             launch[k].fire=a+b; 33             launch[k].fly=b; 34             launch[k].dam=c; 35             sum+=c; 36             k++; 37         } 38     } 39     for(LL i=0;i<m;++i){ 40         scanf("%I64d%I64d%I64d",&launch[k].fire,&launch[k].fly,&launch[k].dam); 41         sum+=launch[k].dam; 42         k++; 43     } 44     for(LL i=0;i<k;++i){ 45         LL fire=launch[i].fire; 46         LL fly=launch[i].fly; 47         launch[i].l=fire+fly; 48         LL t=2*fly; 49         if(fire+t<X||fire+t>X+Tb){ 50             launch[i].r=launch[i].l; 51         }else{ 52             LL len=X+Tb-fire; 53             LL times=len/t; 54             launch[i].r=launch[i].l+times*t; 55         } 56     } 57     for(LL i=0;i<k;++i){ 58         if(launch[i].r-launch[i].l<=Ta){ 59             p[pt].times=launch[i].l; 60             p[pt].index=pt/2; 61             p[pt++].v=launch[i].dam; 62             p[pt].times=launch[i].r; 63             p[pt].index=pt/2; 64             p[pt++].v=launch[i].dam; 65         } 66     } 67     sort(p,p+pt,cmp); 68 } 69 int main(void){ 70     while(~scanf("%I64d%I64d",&Ta,&Tb)){ 71         init(); 72         LL Max=0; 73         LL temp=0; 74         LL l=0,r=0,L=p[0].times; 75         /*************防护罩L=p[0].times时的情况*************/ 76         for(;r<pt&&p[r].times<=R;++r){ 77             LL idx=p[r].index; 78             if(!vis[idx])vis[idx]=1;//[L,R]内有且只有一个idx,即l在[L,R]内 79             else if(vis[idx]){//如果[L,R]内已经有一个idx,说明当前整个区间[l,r]都在[L,R]内 80                 vis[idx]=0; 81                 temp+=p[r].v; 82             } 83         } 84  85         /*****************将防护罩的L不断右移****************/ 86         if(Max<temp)Max=temp; 87         while(r<pt){ 88             LL idx=p[l].index;//防护罩L右移,删去l 89             if(!vis[idx]){//若vis[idx]为零,说明[L,R]中原来有两个idx,即现在[l,r]并不都在[L,R]内 90                 vis[idx]=1; 91                 temp-=p[l].v; 92             }else if(vis[idx])vis[idx]=0;//原来[l,r]就不都在[L,R]内 93             l++; 94             while(l<pt&&p[l].times==p[l-1].times){//如果更改后的l与l-1相同,则需要继续处理 95                 idx=p[l].index; 96                 if(!vis[idx]){ 97                     vis[idx]=1; 98                     temp-=p[l].v; 99                 }else if(vis[idx])vis[idx]=0;100                 l++;101             }102             if(l==pt)break;103             L=p[l].times;104             for(;r<pt&&p[r].times<=R;++r){105                 idx=p[r].index;106                 if(!vis[idx])vis[idx]=1;107                 else if(vis[idx]){108                     vis[idx]=0;109                     temp+=p[r].v;110                 }111             }112             if(Max<temp)Max=temp;113         }114         printf("%I64d\n",sum-Max);115     }116 }
View Code

      然而出了点问题,昨天晚上debug到三点多,一直是WA,会不会写搓了?第二天起来看了好久没看出来,会不会是算法错了?问了游少,他也表示母鸡。

      回到寝室,心血来潮把I64d改成lld交了一发:PE.???.jpg

      全部改成了cin,cout:AC.浪费了我一天技术分享

代码如下:

  1 #include<iostream>  2 #include<algorithm>  3 #include<cstring>  4 #define N 20005  5 #define R (L+Ta)  6 using namespace std;  7 typedef long long LL;  8 LL Ta,Tb,X,n,m,k,sum,pt;  9 bool vis[50005]; 10 struct point{ 11     LL times,index,v; 12 }p[50005]; 13 struct node{ 14     LL fire,fly,dam; 15     LL l,r; 16 }launch[N]; 17 bool cmp(point a,point b){ 18     return a.times<b.times; 19 } 20 void init(){ 21     sum=0; 22     memset(vis,0,sizeof(vis)); 23     memset(p,0,sizeof(p)); 24     memset(launch,0,sizeof(launch)); 25     cin>>X; 26     cin>>n>>m; 27     k=pt=0; 28     for(LL i=0;i<n;++i){ 29         LL a,b,c; 30         cin>>a>>b>>c; 31         if(X<=a+b&&a+b<=X+Tb){ 32             launch[k].fire=a+b; 33             launch[k].fly=b; 34             launch[k].dam=c; 35             sum+=c; 36             k++; 37         } 38     } 39     for(LL i=0;i<m;++i){ 40         cin>>launch[k].fire>>launch[k].fly>>launch[k].dam; 41         sum+=launch[k].dam; 42         k++; 43     } 44     for(LL i=0;i<k;++i){ 45         LL fire=launch[i].fire; 46         LL fly=launch[i].fly; 47         launch[i].l=fire+fly; 48         LL t=2*fly; 49         if(fire+t<X||fire+t>X+Tb){ 50             launch[i].r=launch[i].l; 51         }else{ 52             LL len=X+Tb-fire; 53             LL times=len/t; 54             launch[i].r=launch[i].l+times*t; 55         } 56     } 57     for(LL i=0;i<k;++i){ 58         if(launch[i].r-launch[i].l<=Ta){ 59             p[pt].times=launch[i].l; 60             p[pt].index=pt/2; 61             p[pt++].v=launch[i].dam; 62             p[pt].times=launch[i].r; 63             p[pt].index=pt/2; 64             p[pt++].v=launch[i].dam; 65         } 66     } 67     sort(p,p+pt,cmp); 68 } 69 int main(void){ 70     while(cin>>Ta>>Tb){ 71         init(); 72         LL Max=-1; 73         LL temp=0; 74         LL l=0,r=0,L=p[0].times; 75         for(;r<pt&&p[r].times<=R;++r){ 76             LL idx=p[r].index; 77             if(!vis[idx])vis[idx]=1; 78             else if(vis[idx]){ 79                 vis[idx]=0; 80                 temp+=p[r].v; 81             } 82         } 83         if(Max<temp)Max=temp; 84         while(r<pt){ 85             LL idx=p[l].index; 86             if(!vis[idx]){ 87                 vis[idx]=1; 88                 temp-=p[l].v; 89             }else if(vis[idx])vis[idx]=0; 90             l++; 91             while(l<pt&&p[l].times==p[l-1].times){ 92                 idx=p[l].index; 93                 if(!vis[idx]){ 94                     vis[idx]=1; 95                     temp-=p[l].v; 96                 }else if(vis[idx])vis[idx]=0; 97                 l++; 98             } 99             if(l==pt)break;100             L=p[l].times;101             for(;r<pt&&p[r].times<=R;++r){102                 idx=p[r].index;103                 if(!vis[idx])vis[idx]=1;104                 else if(vis[idx]){105                     vis[idx]=0;106                     temp+=p[r].v;107                 }108             }109             if(Max<temp)Max=temp;110         }111         cout<<sum-Max<<endl;112     }113 }

 

Countries