lightoj 1072 Calm Down | 二分

本文主要是介绍lightoj 1072 Calm Down | 二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

与lightoj 1048 基本一样，不过是这题是弱化版，不用输出方案。

http://blog.csdn.net/u011580493/article/details/38958267

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e3+5;
const int INF = 0x3f3f3f3f;
int n, m;
int a[MAXN];
bool OK(int mid)
{int i = 0, tsum, cot = 0;while(i < n){tsum = 0;for(;i < n; i++){if(tsum + a[i] <= mid)tsum += a[i];elsebreak;}cot++;if(cot > m)     return false;}if(cot <= m)return true;return false;
}
int main()
{ios::sync_with_stdio(false);int T, cas = 0;cin>>T;while(T--){cin>>n>>m;int tsum = 0;for(int i = 0;i < n; i++)cin>>a[i], tsum += a[i];//int l = 0, r = tsum;int ans;while(l <= r){int mid = (l+r)/2;if(OK(mid))ans = mid, r = mid-1;elsel = mid+1;}cout<<"Case "<<++cas<<": "<<ans<<endl;}return 0;
}

这篇关于lightoj 1072 Calm Down | 二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---