[PA2014]Muzeum

题目大意：

有\(n\)件展品和\(m\)个警卫，每件展品有一个坐标\((x_i,y_i)\)和价值\(v_i\)，每个警卫的坐标为\((x_i,y_i)\)。每个警卫面朝\(y\)轴负方向，左右视角都为\(\theta\)，警卫视线范围内的展品不能偷。你可以收买一些警卫，使其放弃安保工作，收买第\(i\)个警卫的价格为\(v_i\)。你需要收买一些警卫并偷走一些展品，求盗取的总价值\(-\)收买的支出的最大值。

思路：

\(\tan(\theta)=\frac wh\)，将所有点的\(x_i\)乘上\(h\)，\(y_i\)乘上\(w\)，再将所有点绕原点顺时针旋转\(45^\circ\)，则展品\((u_i,v_i)\)被\((x_i,y_i)\)上的警卫监视，当且仅当\(u_i\le x_i\)且\(v_i\le y_i\)。

将警卫当作“水源”，含\(v_i\)体积的水；展品当作“水桶”，容量为\(v_i\)。答案即为所有“水桶”容量之和\(-\)能被水桶吸收的水的体积。

从左到右枚举每一个警卫，set中以纵坐标为序维护警卫左边的水桶的剩余容量。从高到低枚举不高于警卫所在位置的水桶，并尽可能将水装满即可。

源代码：

#include
    
     #include
     
      #include
      
       #include
       
        inline int getint() {    register char ch;    register bool neg=false;    while(!isdigit(ch=getchar())) neg|=ch=='-';    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return neg?-x:x;}typedef long long int64;const int N=2e5+1;struct Point {    int64 x,y;    int v;    bool operator < (const Point &rhs) const {        return x==rhs.x?y
        
         
           > set;int main() { const int n=getint(),m=getint(); const int w=getint(),h=getint(); int64 ans=0; for(register int i=1;i<=n;i++) { const int64 x=1ll*getint()*h,y=1ll*getint()*w; a[i].x=x+y; a[i].y=y-x; a[i].v=getint(); ans+=a[i].v; } for(register int i=1;i<=m;i++) { const int64 x=1ll*getint()*h,y=1ll*getint()*w; b[i].x=x+y; b[i].y=y-x; b[i].v=getint(); } std::sort(&a[1],&a[n]+1); std::sort(&b[1],&b[m]+1); for(register int i=1,j=1;i<=m;i++) { for(;j<=n&&a[j].x<=b[i].x;j++) { set.insert(std::make_pair(a[j].y,a[j].v)); } while(b[i].v) { std::set
          
           
             >::iterator it=set.lower_bound(std::make_pair(b[i].y+1,0)); if(it==set.begin()) break; std::pair
            
              p=*--it; set.erase(it); const int tmp=std::min(p.second,b[i].v); b[i].v-=tmp; p.second-=tmp; ans-=tmp; if(p.second) set.insert(p); } } printf("%lld\n",ans); return 0;}