CF 551c 二分搜索+思维题-白红宇

CF 551c 二分搜索+思维题

阅读量：4112 次

发布时间：2019-05-25

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

题意：m个人要去移动n堆盒子每堆上有若干个盒子每个人只能进行两种操作从一个位置走到下一个位置如果这个位置上的盒子个数不为0 那么就要把这个位置上的盒子移掉每种操作需要一秒

求这m个人把盒子全都清掉所花的最少时间；

#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
            #include 
            
              #include 
             
               using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=50000; ll max(int a,int b) {return a>b?a:b;}; ll min(int a,int b) {return a
              
               =mid) return false;//不可到达 ll cnt=m-1,s=0; for(int i=1;i<=t;i++) { s+=a[i];//该人需要搬动的箱子数目 while(s+i>mid)//因为s>mid-i；所以s-(mid-i)>0的，即每加入一个人他其实在mid时间内一直在都搬箱子 { cnt--; s-=(mid-i);//增加一个人，那么在时间限制为mid，已走了i的情况下最多能帮他搬mid-i个 if(cnt<0) return false; } } return true; } int main() { while(~scanf("%d %d",&n,&m)) { s=0,t=-1; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[i]>0) t=i; s+=a[i]; } ll l=-1,r=s+t;//二分搜索 左开右闭区间 while(r-l>1) { ll mid=(l+r)>>1; if(ok(mid)) r=mid; else l=mid; } printf("%lld\n",r); } return 0; }

思路：本题的做法非常奇妙，1.先二分枚举可能的时间，然后再判断在该时间内能否搬走所有的箱子；

2.判断时，先假想有一个人一直往右走，然后再逐个加人。

3.如果t>mid的话，那么mid-t>0无论怎样搬都是不可实现的，如果t<mid的话，mid-t>0那么只要人数足够多，都能对在t位置

的箱子造成减少。

转载地址：http://wxgsi.baihongyu.com/

你可能感兴趣的文章