最优分割

// 结果在（max(nums),sum(nums))之间，使用二分查找
// 以[7,2,5,10,8]举例，开始假设只有一个子数组,set=1 
// 第一个 mid = (10+32)/2=21, 然后把数字一个一个塞进去 
// 先塞7, 7<21, 7+2<21, 7+2+5<21, 直到 7+2+5+10>21
// 意味着一个数组放不下, set+1=2, 然后把后面的塞完
// 如果比m大说明我们开的子数组太多, 也就意味值我们数组容量(mid)太小 
// 所以我们就从[22,32]区间中找, 否则在[10,21]中找  


import java.util.Scanner;
public class Main {
    public static int splitArray(int[] nums, int m) {
        int max = Integer.MIN_VALUE, sum = 0;
        for (int i : nums){
            sum += i;
            max = Math.max(max,i);
        }
        
        int left = max, right = sum;
        int mid, set, cur;
        while(left < right){
            mid = (left+right)/2;
            // m 是子数组数，不是cut数
            set = 1;
            cur = 0;
            for(int i : nums){
                if(cur+i > mid){
                    set++;
                    cur = 0;
                }
                cur+= i;
            }
            if(set > m) left = mid + 1;
            else right = mid;
        }
        return left;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] nums = new int[n];
        for (int i=0; i<n; i++){
            nums[i] = sc.nextInt();
        }
        System.out.print(splitArray(nums,m));
    }
} 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution25_最优分割 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = bf.readLine().split(" ");
        int n = Integer.parseInt(line1[0]);
        int m = Integer.parseInt(line1[1]);
        String[] line2 = bf.readLine().split(" ");
        int[] nums = new int[n];
        int sum = 0;
        int max = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(line2[i]);
            if (max < nums[i]) {
                max = nums[i];
            }
            sum += nums[i];
        }
        System.out.println(binarySearch(nums, m, n,max,sum));

    }

    /**
     * 二分逼近法
     * 这个题的意思：假设存在数组 1 4 2 3 5 分割成 3 段，有几种分法呢，答案是 C4^2: 4*3/2*1 = 6 种，
     * 即在数组的四个间隔中插入两根柱子将其分成 3 段，每一种分法中会对应有 3 个子数组的值，其中最大的值即为当前分割方法的
     * 最大权值，在所有的分割方法中找出最小的一个最大权值，听起来好像有点绕口...
     * eg：1  |  4 2 | 3 5 这种分割方法，它的最大权值为 8 而： 1 4 | 2 3 | 5 分割方法，它的最大权值为 5
     *
     *
     * 思路：假设存在一个最大值的最小值 x,反过来划分数组。子数组的权值都比x要小，如果组数小于m，说明 x 还可以再小；
     * 组数大于m，说明 x 需要变大，以容纳更多的数。减小分组数。如果组数等于m，x也可能再小
     * 考虑边界情况，现在把每个元素分成一组，那么x的最小值就是数组中最大的值；把数组当成一个组，那么x就是数组元素之和。
     * 即 max(nums) <= x <= sum(nums)
     * 因为每一组都是连续的，只要每一组累加的和大于了x，那么当前元素就要放到下一组，记录有多少组即可。
     *
     * 我们通过二分逼近来确定这个x的值。
     * 在于这个“逼近”，这道题是在连续的数值范围中逼近，换句话说，每个组的和一定在范围之内，因此正确答案是不会被跳过的；
     */
    private static int binarySearch(int[] nums, int m, int n, int left, int right) {
        int ans = right;
        while (left <= right) {
            int mid = (left + right) / 2;
            int sum = 0;
            int count = 1;//记录数组的个数
            for (int i = 0; i < n; i++) {
                //直到当前子数组的和加上当前元素比mid还大，那必须将当前元素归为下一个子数组中，sum重新计算新子数组的和
                if (sum + nums[i] > mid) {
                    count++;
                    sum = nums[i];
                } else {//当前子数组的和比mid小，继续加
                    sum += nums[i];
                }
            }
            //如果分完之后组数小于等于m说明，mid还可以更小，即上面思路里说的x还能更小 右区间缩小到mid-1；
            if (count <= m) {
                ans = Math.min(ans, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }


    /**
     * 方法一：动态规划 此方法在牛客网上没全通过，但是是一种正确的结题思路
     */
    private static int splitArray(int[] nums, int n, int m) {
        int[][] dp = new int[n + 1][m + 1];//dp[i][j]表示前面i个数被分成m个区间中最小的权值
        int[] sub = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < n; i++) {
            sub[i + 1] = sub[i] + nums[i];//前面i个元素的和
        }
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 0; k < i; k++) {
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], sub[i] - sub[k]));
                }
            }
        }
        return dp[n][m];
    }
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    int Max = INT_MIN,sum=0;
    cin>>n>>m;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
        Max =  max(Max,a[i]);
    }
    int left = Max,right = sum;
    int cnt;
    int t;
    while(left<right)
    {
        cnt = 1;
        t = 0;
        int mid  = (left+right)>>1;
        for(int i=0;i<n;i++)
        {
            if(t+a[i]>mid)
            {
                cnt++;
                t=0;
            }
            t+=a[i];
        }
        if(cnt>m)
            left=mid + 1;
        else right = mid;
            
    }
    cout<<left<<endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int a[n],sum=0,b[m],ma=INT_MIN;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
        ma=max(ma,a[i]);
    }
    int left=ma,right=sum,mid,set, cur;
    while(left<right)
    {
        mid=(left+right)/2;
        set = 1;
        cur = 0;
        for(int i=0;i<n;i++)
        {
            if(cur+a[i]>mid)
            {
                set++;
                cur = 0;
            }
            cur+=a[i];
        }
        if(set > m) 
            left = mid + 1;
        else 
            right = mid;
    }
    cout<<left;
    return 0;
}

n, m = map(int, input().split())
num = list(map(int, input().split()))
left = max(num)
right = sum(num)
ans = right
while left < right:
    res = 0
    cnt = 1
    mid = (left+right)//2
    for i in range(len(num)):
        if res+num[i] > mid:
            cnt += 1
            res = num[i]
        else:
            res += num[i]
    if cnt <= m:
        ans = min(mid, ans)
        right = mid
    else:
        left = mid + 1
print(ans)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,s=0,Max=INT_MIN;
    cin>>n>>m;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        s += a[i];
        Max = max(Max, a[i]);
    }
    int l=Max,r=s,mid,cnt,t;
    while(l<r){
        mid = (l+r)/2;
        cnt = 1;
        t = 0;
        for(int i=0;i<n;i++){
            if(t+a[i]>mid){
                cnt++;
                t = 0;
            }
            t += a[i];
        }
        if(cnt>m)
            l = mid + 1;
        else
            r = mid;
    }
    cout<<l<<endl;
    return 0;
}

import java.util.*;
public class Main{
    //判断nums序列能不能被分割为最大子序列和为part的m段
    public static boolean isSuccess(int[] nums,int part,int m){
        int cnt=m,partSum=0;
        int i,j;
        for(i=0;i<nums.length;){
            if(cnt<=0) return false;
            for(j=i;j<nums.length;j++){
                partSum+=nums[j];
                if(partSum>part){
                    partSum-=nums[j];
                    j--;
                    cnt--;
                    break;
                }
                else {
                	if(j==nums.length-1){
                        cnt--;
                        return true;
                    }
                }
            }
            i=j+1;
            partSum=0;
        }
        return false;
    }
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int sum=0,min=10000,res=0;
        int n=in.nextInt(),m=in.nextInt();
        in.nextLine();
        int[] nums=new int[n];
        for(int i=0;i<n;i++){
            nums[i]=in.nextInt();
            min=Math.min(min,nums[i]);
            sum+=nums[i];
        }
        in.nextLine();
        in.close();

        if(m==1){
            res=sum;
        }else{
            int resMin=sum/m;
            for(int i=resMin;i<=sum-min;i++){
                if(isSuccess(nums,i,m)==true){
                    res=i;
                    break;
                }
            }
        }
        System.out.println(res);
    }
}

n, k = list(map(int, input().strip().split(" ")))
nums = list(map(int, input().strip().split(" ")))
 
left, right = max(nums), sum(nums)
res = right
while left <= right:
    mid = (left + right)//2
    cnt = 1
    sum_ = 0
    for i in range(n):
        if nums[i] + sum_ > mid:
            sum_ = nums[i]
            cnt += 1
        else:
            sum_ += nums[i]
    if cnt <= k:
        res = min(res,mid)
        right = mid - 1
    else:
        left = mid + 1
print(res)