2016"百度之星" - 复赛（Astar Round3） 1003 拍照

时间：2022-02-09 14:30:10

拍照

思路：先静态，离线树状数组，分别统计每个点向左向右能看到的船的数量。再枚举整个区间求最大值。

应为人和船都是动态的，假设船往左走，处理每个点看到向左最大船的数量，满足动态条件。就是向左的船一开始在最右边，向右的船一开始在最左边，则两船肯定相向运动到某个地方最佳。

 //#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <set>

 #include <utility>

 #include <algorithm>

 #include <vector>

 #include <map>

 // #include<malloc.h>

 using namespace std;

 #define clc(a,b) memset(a,b,sizeof(a))

 #define LL long long

 void fre() { freopen("in.txt","r",stdin);}

 const int inf = 0x3f3f3f3f;

 const double eps = 1e-;

 const double pi = acos(-);

 const LL MOD = 1e9+;

 // const LL p = 1e9+7;

 // inline int r(){

 //     int x=0,f=1;char ch=getchar();

 //     while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}

 //     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

 //     return x*f;

 // }

 const int N = ;

 struct  node{

    int x,y,z,d;

 }a[N];

 int sum1[N],sum2[N];

 int summ[N];

 int p[N<<];

 int main(){

     // fre();

     int t,n,X,Y,Z,D;

     scanf("%d",&t);

     int cas;

     cas=;

     while(t--){

         clc(sum1,);

         clc(sum2,);

         clc(summ,);

        scanf("%d",&n);

        int k;

        k=;

        for(int i=;i<n;i++){

           scanf("%d%d%d%d",&X,&Y,&Z,&D);

           if(X+Z>=Y-Z){

              p[++k]=X+Z;

              p[++k]=Y-Z;

           }

           a[i].d=D;

           a[i].x=X;

           a[i].y=Y;

           a[i].z=Z;

        }

        sort(p+,p+k+);

        k=unique(p+,p+k+)-p-;

        for(int i=;i<n;i++){

           if(a[i].d==-&&a[i].y-a[i].z<=a[i].x+a[i].z){

              sum1[lower_bound(p+,p+k+,a[i].y-a[i].z)-p]++;

              sum1[lower_bound(p+,p+k+,a[i].x+a[i].z)-p+]--;

           }

           else if(a[i].d==&&a[i].y-a[i].z<=a[i].x+a[i].z){

              sum2[lower_bound(p+,p+k+,a[i].y-a[i].z)-p]++;

              sum2[lower_bound(p+,p+k+,a[i].x+a[i].z)-p+]--;

           }

        }

        for(int i=;i<=k;i++){

           sum1[i]+=sum1[i-];

           sum2[i]+=sum2[i-];

        }

        for(int i=k;i>=;i--){

           summ[i]=max(summ[i+],sum1[i]);

        }

        int ans=;

        for(int i=;i<=k;i++){

           ans=max(ans,sum2[i]+summ[i]);

        }

        printf("Case #%d:\n%d\n",++cas,ans);

     }

     return ;

 }

相关文章