Codeforces 551C GukiZ hates Boxes 二分答案-白红宇

Codeforces 551C GukiZ hates Boxes 二分答案

阅读量：4342 次

发布时间：2019-06-07

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

题意：

一共同拥有n个空地（是一个数轴，从x=1 到 x=n)，每一个空地上有a[i]块石头

有m个学生

目标是删除全部石头

一開始全部学生都站在 x=0的地方

每秒钟每一个学生都能够在原地删除一块石头，或者向 → 移动一格距离

问：删除全部石头的最短时间

案例解析：

3 2

1 0 2

第一个学生第一秒向→走。第二秒删a[1]的一块石头

第二个学生一直走到头。删掉a[3] ，所以第二个学生花费是 1+1+1+2 = 5

两个学生能够同一时候运动。

思路：

二分答案，设答案为x。即须要x秒来搬完石头

先拿一个学生来

总要有一个学生来搬最远的那堆石头的

先让这个学生走到尽头

这个学生拥有的时间就是x

那么走到尽头后，还剩下的时间用来搬最后一堆石头

假设这堆石头搬不完，那么这个学生就利用完了，换一个学生

假设搬的完那么这个学生还剩下的时间能够用来搬前一堆石头一直把这个学生利用完。

假设全部学生都利用完了石头还是搬不完，那么x秒肯定是不够的

否则x秒就是够的

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;template 
                   
                    inline bool rd(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1;}template 
                    
                     inline void pt(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) pt(x / 10); putchar(x % 10 + '0');}typedef long long ll;typedef pair
                     
                       pii;const int inf = 1e9;const int N = 1e5 + 10;int n, m;int a[N], b[N];bool ok(ll x) { for (int i = 1; i <= n; i++)b[i] = a[i]; int top = n, tmp = m; while (tmp-->0 && top) { ll lef = x - top; while (lef && top) { if (b[top] == 0) { top--;continue; } if (b[top] <= lef) { lef -= b[top--]; } else { b[top] -= (int)lef;lef = 0; } } } while (top && b[top] == 0)top--;//找到最后一个而且不是0的点 return top == 0;}int main() { rd(n); rd(m); int d = 1; for (int i = 1; i <= n; i++) { rd(a[i]); } while (a[n] == 0)n--; //把最后的0删掉 ll l = 1, r = 1e15, ans; while (l <= r) { ll mid = (l + r) >> 1; if (ok(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } pt(ans); return 0;}