G - 数组划分游戏 HihoCoder - 1948

小Hi在玩一个有关数组划分的游戏。给定一个整数K和一个长度为N的数组A=[A1, A2, ... AN]，小Hi需要将它划分为K个连续子数组，并对每个子数组求和。

不妨设这K个子数组的和依次是S1, S2, ... SK，则小Hi的得分是其中的最小值即min(S1, S2, ... SK)。  

例如对于A=[1, 2, 3, 4]和K=2，小Hi可以划分成[1, 2]和[3, 4]，这样得分是3；也可以划分成[1, 2, 3]和[4]，这样得分是4。

对于给定的K和数组A，你能帮助小Hi算出他最多能得多少分吗？

Input

第一行包含两个整数N和K。  

第二行包含N个整数A1, A2, ... AN。  

对于60%的数据，1 <= N <= 1000  

对于100%的数据，1 <= K <= N <= 100000  1 <= Ai <= 1000000

Output

一个整数代表答案

Sample Input

4 2 1 2 3 4

Sample Output

4

题意：输入n,k代表数组有n个数，分为k组，每组里面为和，取k组中的最小值；

ps：此题利用二分法，真是高手啊，本菜鸡，第一次遇到这种题目，甚妙；

大概就是二分找最小值mid；只要符合条件，就赋给ans；如果cnt次数能到达k，代表mid小， 故l=mid+1；r同理；

不断的进行二分当mid正好满足条件的时候，诶！！成功，此时mid就是最大能满足条件的；

#include <iostream> #include <algorithm> #include <stack> #include <stdio.h> using namespace std; #define ll long long int const int N = 100005; int a[N]; int l; int n,k; bool check(ll t) { ll re=0,cnt=0; for(int i=1;i<=n;i++) { re+=a[i]; if(re>=t) //如果大于mid的次数很多，则mid小了 { re=0; cnt++; if(cnt==k)return true; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k; ll sum=0,ans; for(int i=1;i<=n;i++) { cin>>a[i]; sum+=a[i]; } ll mid; while(l<=sum)//二分法找mid, { mid=(l+sum)>>1; if(check(mid)){ ans=mid; l=mid+1; } else{ sum=mid-1; } } cout<<ans<<endl; return 0; }