Trace 2018徐州icpc网络赛思维+二分-白红宇

Trace 2018徐州icpc网络赛思维+二分

阅读量：7072 次

发布时间：2019-06-28

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

There's a beach in the first quadrant. And from time to time, there are sea waves. A wave (

Input

The first line is the number of waves $\le 50000)n(n≤50000).$

The next $\le 10000000y≤10000000 )，the ii-th line means the ii-th second there comes a wave of ( xx , yy ), it's guaranteed that when 1 \le i1≤i , j \le nj≤n，x_i \le x_jxi≤xj and y_i \le y_jyi≤yj don't set up at the same time.$

Output

An Integer stands for the answer.

Hint：

As for the sample input, the answer is

样例输入复制

31 44 13 3

样例输出复制

题目来源

题意：有n次海浪，每次海浪会产生两段轨迹(0,y)到(x,y)和(x,0)到(x,y)，后面的海浪会将前面的在(0,0)到(x,y)之间区域的海浪轨迹覆盖掉，问最后剩余的轨迹长度

分析：每段轨迹有效的贡献是在此轨迹被接下来所有轨迹覆盖一次后剩余的轨迹长度

　　所以我们考虑直接从后面往前面枚举

　　最后的轨迹长度肯定是可以直接加上的，没有其余的海浪能覆盖掉他，然后将其的轨迹点放进集合

　　接下来遍历到的点只要看集合里比他小的最大的数就是能覆盖掉他多少长度，减去这个长度就行

AC代码：

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define ls (r<<1)#define rs (r<<1|1)#define debug(a) cout << #a << " " << a << endlusing namespace std;typedef long long ll;const ll maxn = 1e5+10;const ll mod = 2e9+7;const double pi = acos(-1.0);const double eps = 1e-8;ll f( vector
                  
                    e ) { ll sz = e.size(), ans = 0; set
                   
                     s; for( ll i = sz-1; i >= 0; i -- ) { set
                    
                     ::iterator it = s.lower_bound(e[i]); if( it == s.begin() ) { ans += e[i]; } else { it --; ans += e[i] - *it; } s.insert(e[i]); } return ans;}int main() { ll x, y, n; vector
                     
                       e1, e2; scanf("%lld",&n); while( n -- ) { scanf("%lld%lld",&x,&y); e1.push_back(x), e2.push_back(y); } printf("%lld\n",f(e1)+f(e2)); return 0;}

转载于:https://www.cnblogs.com/l609929321/p/9614868.html

你可能感兴趣的文章