文明距离（civil）

全栈程序员-站长 • 2026年3月16日下午3:13 • 未分类 • 阅读 2

你被一个一向箔打中了，现在你掉到了一个一维空间中，也就是一个数轴上。

在这个数轴上，每秒会在一段连续的区间上出现“文明”。而你在每一秒开始的时候，可以花费x的代价移动x的距离，其中x是任意非负实数。当你移动结束以后，若你离“文明”的距离为y，你就需要花费y的代价使用“大眼睛”来观测这个文明，不然你就要被黑暗森林攻击了。此处距离是指你到这段区间中任意一点的距离的最小值。

现在，你收到了一系列信息，表明每秒的文明出现位置以及你的初始位置，请你最小化你的代价来完成任务。

第一行两个正整数n,x，分别表示总秒数以及你的初始位置。

接下来n行，第i+1行有两个正整数li,ri，表示第i秒的时候的文明出现的位置。

输出一行，表示最小代价。

样例输入

5 4 2 7 9 16 8 10 9 17 1 6

样例输出

对于20%的数据，n<=10，x,li,ri<=10；

对于50%的数据，n<=2000,x,li,ri<=10^9；

对于100%的数据，n<=5*10^5,x,li,ri<=10^9。

solution

orzxjq！！！！！

3分钟屠出我永远也做不出的题。

我们假设我们现在的最优取值区间[l,r]

新来的一段区间为[a,b]

如果abcd有交集，那么下一步的最优解区间就是交集。

否则下一步的最优解区间是两个区间中间的那一段。

#include
         
       
         
         
         
         
         
          
        
          
          
          
          
           #include
          
        
          
          
          
          
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
               #define maxn 500005 
               using 
               namespace 
                std;  
               int 
                n,x,l[maxn],r[maxn];  
               long 
               long 
                ans;  
               int 
                main() { cin>>n>> 
               x;  
               int nl=x,nr= 
               x;  
               for( 
               int i= 
               1;i<=n;i++ 
               ){ scanf( 
               " 
               %d%d 
               ",&l[i],& 
               r[i]);  
               if(nr< 
               l[i]){ ans+=l[i]- 
               nr; nl=nr;nr= 
               l[i]; }  
               else 
               if(nl> 
               r[i]){ ans+=nl- 
               r[i]; nr=nl;nl= 
               r[i]; }  
               else 
                { nl=max(nl,l[i]);nr= 
               min(nr,r[i]); } } cout< 
               
                 endl; 
                return 
                0 
                ; }

View Code

转载于:https://www.cnblogs.com/liankewei/p/10409279.html

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/230058.html原文链接：https://javaforall.net

文明距离（civil）