1521 一维战舰-白红宇

1521 一维战舰

阅读量：4705 次

发布时间：2019-06-10

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

思路：依次把x【】数组的元素加入set，再二分出当前入set元素在set中的上界r和下界l,则这段区间能放的最多的战舰数量就由原来的（r-l)/(a+1)减少为（x[i]-l）/(a+1)+(r-x[i])/(a+1),

每次判断加入新元素后能放最多战舰数sum与k的大小即可。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #include 
                  
                   14 #include 
                   
                    15 #include 
                    
                     16 #define x first17 #define y second18 #define pb push_back19 #define mp make_pair20 #define lson l,m,rt*221 #define rson m+1,r,rt*2+122 #define mt(A,B) memset(A,B,sizeof(A))23 #define mod 100000000724 using namespace std;25 typedef long long LL;26 const int N=2e5+10;27 const int inf = 0x3f3f3f3f;28 const LL INF=0x3f3f3f3f3f3f3f3fLL;29 int x[N];30 set
                     
                       Q;31 int solve(int l,int k)32 {33 if(l
                      
                       >n>>k>>a;43 cin>>m;44 for(int i=1;i<=m;i++)scanf("%d",&x[i]);45 Q.insert(0);Q.insert(n+1);46 sum=solve(n,a);47 for(int i=1;i<=m;i++)48 {49 set
                       
                        ::iterator it1,it2,it3,it;50 Q.insert(x[i]);51 it1=Q.find(x[i]);52 it1--;53 it2=Q.find(x[i]);54 it2++;55 sum=sum-solve(*(it2)-*(it1)-1,a)+solve(x[i]-*(it1)-1,a)+solve(*(it2)-x[i]-1,a);56 if(sum