269D Maximum Waterfall-白红宇

269D Maximum Waterfall

阅读量：6341 次

发布时间：2019-06-22

本文共 1344 字，大约阅读时间需要 4 分钟。

题目大意

给出一些墙，水从高往低流，每次只能到达一面墙，选择一个路径，使得路径上的流量的最小值最大。

分析

这是一道经典的扫描线题，我们发现能够合法的线段对数至多只有n对。将一条线段拆成两个点，自左向右排序依次加入set中，按照高度关系将它们相连，详见代码（也可以用线段树做这道题，有时间再补吧qwq）。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;#define sp cout<<"---------------------------------------------------"<
                   
                    ev;set
                    
                     
                       >s;vector
                      
                       g[210000];vector
                       
                        c[210000];int ans[210000],le[210000],ri[210000];inline int what(int x,int y){ return (min(ri[x],ri[y])-max(le[x],le[y]));}inline int work(int x){ if(ans[x]!=-1)return ans[x]; if(x==1)return inf; int res=0; for(int i=0;i<(int)g[x].size();i++) res=max(res,min(c[x][i],work(g[x][i]))); return ans[x]=res;}int main(){ int n,m,i,H,L,R; scanf("%d%d",&n,&m); n+=2; le[0]=le[1]=-inf; ri[0]=ri[1]=inf; for(i=2;i
                        
                          >::iterator it= s.insert(make_pair(ev[i].h,ev[i].id)).first; int dw=(--it)->second; it++; int up=(++it)->second; if(g[up].size()&&g[up].back()==dw){ g[up].pop_back(); c[up].pop_back(); } g[up].push_back(ev[i].id); c[up].push_back(what(ev[i].id,up)); g[ev[i].id].push_back(dw); c[ev[i].id].push_back(what(ev[i].id,dw)); } } memset(ans,-1,sizeof(ans)); cout<
                         
                          <

转载于:https://www.cnblogs.com/yzxverygood/p/9341265.html

你可能感兴趣的文章