P4803 【[CCO 2015]太阳能飞行】

发表于 | 更新于 | 分类于 ，

说实话，这道题是我随机跳到的。初看觉得不难，结果在码代码的时候遇到很多问题。最后，八WA之后终见AC。这一定是我太蒟了

题意

我觉得本题题意也是一大难点，所以在看题目时要逐字，多看几遍。我在做的过程中，看错了两遍题目（前车之鉴），可能是本人的语文不好

本题的意思大概就是，在一个坐标系中，有n架飞机直线飞行（当然不是匀速），给定X坐标范围，又给定每架飞机的起始高度和终止高度。（其实就相当于n条一次函数的图象）。每架飞机还有一个干扰值，表示影响它正下方的飞机太阳吸收能力的强弱。现有Q个问题，请你求出区间[Si,Si+K]中，第Pi架飞机的太阳能板吸收的太阳光减少的值。我所说的难理解的地方就在这里。这里要求的并不是只要在该区间范围内能出现在第Pi架飞机上方的飞机。而是要求该区间中的每一时刻的减少的值中的最大值（可以这么理解）。

$\large\mathcal{Solution}$

刚开始真的无从下手，然后就看到。。。

这才有点眉目。

对于n架飞机，我们可以预处理出每两架飞机航线（相当于一次函数）之间的关系（要么相交，要么不相交）。而只要两架飞机不在相交点上，就一定存在其中一架飞机对另外一家飞机有影响。也就是说，任何一架飞机对于一架它可以影响的飞机，影响的范围只可能是 [0,相交点),(相交点,X]（相交的情况）、[0,X]（不相交的情况）。

知道了可影响范围的计算，于是一个奇妙的想法萌发，前缀和！因为对于一架飞机而言，它的被影响的值只有在经过一个交点后才会改变（因为飞机的相对位置就改变了）。因此，就可以记录下每个影响范围的起点和终点，利用区间加值的方法（这个，相信一般人都会吧）。这时候就可以利用前缀和，造一个前缀和数组，这样就可以得出每架飞机每一个时刻的被影响值。

最后回答问题的时候，只要先利用二分找出起点，然后往后跳，直到终点，中途用一个变量记录最大值即可。（不清楚的请看代码注解）

这样，这道题就解决了。

附:

  • 这是本蒟蒻的第一篇题解，望支持。如有错误或有更优解，请告知。

  • CCO官网上有数据 传送门

  • 这是一篇之前blog搬过来的文章，码风勿喷 嘤嘤嘤

$\large\mathcal{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//本代码中的快读和快输均是之前尝试时加的，没有应该问题不大
//代码中有些地方可能写的有些复杂，可以多考虑考虑
#include<bits/stdc++.h>
#define ff(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
struct xx{
    double x;
    long long val;
}a[2010][2010],f[2010][2010];                         //f 前缀数组
int x,kk,n,Q,b[2010],y[2010],c[2010],l[2010];
long long sum[2010];
double k[2010];
bool cmp(xx s,xx t){
    return s.x<t.x;
}
inline int read(){    //优化读入
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}   
inline void write(long long x) {   //优化输出
    int cnt=0;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int main(){
    x=read();kk=read();n=read();Q=read();
    ff(i,1,n) b[i]=read(),y[i]=read(),c[i]=read(),k[i]=1.0*(y[i]-b[i])/x;     // y[]、b[]对应一次函数y=kx+b中的k、b
    ff(i,1,n-1)
        ff(j,i+1,n){
            int ii=i,jj=j;
            if((b[ii]>b[jj]&&y[ii]<y[jj])||(b[ii]<b[jj]&&y[ii]>y[jj])){      //相交的情况
                if(b[ii]<b[jj]&&y[ii]>y[jj]) swap(ii,jj);
                double dx=1.0*(b[ii]-b[jj])/(k[jj]-k[ii]);       //计算交点（基本操作）
                a[jj][++l[jj]].val=-c[ii];a[jj][l[jj]].x=dx;sum[jj]+=c[ii]; //区间加，并记录下交点，sum数组相当于x=0时的前缀数组的值
                a[ii][++l[ii]].val=c[jj];a[ii][l[ii]].x=dx;                
            }else{                                                          //不相交的情况
                if(b[ii]>b[jj]) swap(ii,jj);
                sum[ii]+=c[jj];                              //同上     
            }
        }
    ff(i,1,n){
        sort(a[i]+1,a[i]+l[i]+1,cmp);          //排序
        long long cc=0;
        int ll=l[i];
        l[i]=0;
        ff(j,1,ll){
            cc+=a[i][j].val;
            if(!(abs(a[i][j].x-a[i][j+1].x)<=1e-7)) f[i][++l[i]].x=a[i][j].x,f[i][l[i]].val=cc+f[i][l[i]-1].val,cc=0; //造前缀数组，并去重
        }
    }
    ff(i,1,Q){     
        int ll,rr;
        x=read();ll=read();
        int l1=1,r1=l[x],st=0;
        rr=ll+kk;
        while(l1<=r1){           //二分找起点
            int mid=(l1+r1+1)/2;
            if(f[x][mid].x<=ll) st=mid,l1=mid+1; else r1=mid-1;
        }           
        long long ans=0;
        for(;st<=l[x]&&f[x][st].x<rr;st++) if(f[x][st].val+sum[x]>ans) ans=f[x][st].val+sum[x]; //点往后跳，找最大值
        write(ans);
        printf("\n");
    }
    return 0;      
}


$\Huge{祝大家RP++！！！}$