TIOJ 1432. 骨牌遊戲

TIOJ 1432. 骨牌遊戲

題目概述:

簡單來說，就是給定一個數列，然後把數列切w刀，使得數列變成w+1塊。

請使每塊的數值總和的最大值 最小。

思路:

基本上就是二分搜答案。假設要詢問能不能切w刀達到最大值最小為x，那就直接從第一個開始加，只要大於x就切，那看到最後有沒有切超過w刀!那要注意的是只要有一個數值大於x那就要直接判成無法達到。

//By SCJ

//tioj 1432

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

int a[1002],n,w;

inline bool ck(int x)

{

   int sum=0,cnt=0;

   for(int i=0;i<n;++i)

   {

       if(a[i]>x) return false;

       if(sum+a[i]>x) cnt++,sum=a[i];

       else sum+=a[i];

   }

   return cnt<=w;

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   while(cin>>n>>w,n!=0)

   {

       for(int i=0;i<n;++i) cin>>a[i];

       int l=0,r=1000000;

       while(l<r)

       {

           int mid=(l+r)/2;

           if(ck(mid)) r=mid;

           else l=mid+1;

       }

       cout<<l<<endl;

   }

}