首页 > 试题广场 >

最优分割

[编程题]最优分割
  • 热度指数:2780 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
依次给出n个正整数A1,A2,… ,An,将这n个数分割成m段,每一段内的所有数的和记为这一段的权重, m段权重的最大值记为本次分割的权重。问所有分割方案中分割权重的最小值是多少?

输入描述:
第一行依次给出正整数n,m,单空格切分;(n <= 10000, m <= 10000, m <= n)
第二行依次给出n个正整数单空格切分A1,A2,… ,An (Ai <= 10000)


输出描述:
分割权重的最小值
示例1

输入

5 3
1 4 2 3 5

输出

5

说明

分割成 1  4 |   2   3  |   5  的时候,3段的权重都是5,得到分割权重的最小值。
// 结果在(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));
    }
} 

编辑于 2019-04-13 17:07:54 回复(0)
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];
    }
}
发表于 2019-08-02 21:10:15 回复(1)
#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;
}

发表于 2019-08-15 20:11:47 回复(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;
}

发表于 2019-07-04 22:18:00 回复(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)

发表于 2019-08-15 10:52:46 回复(0)
#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;
}

发表于 2019-07-16 02:31:48 回复(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);
    }
}

分成m段,题目要求的结果,其实是要尽可能地把序列均分成每一段之和相等。题目要求的结果肯定至少是所有元素之和/m,这种情况是在所给序列本身就可以正好划分成m段且每一段都为sum/m,比如题目给的样例那样。但是如果改变一下样例的顺序,比如改成4 2 1 5 3,分成3段,答案就不是5了,因为想要把序列分成3段而且每段最大值不大于5,是做不到的。那么就尝试一下5+1=6,看能不能分成3段且每段和小于等于6,可以的:4 2 | 1 5 | 3,假设6也不行,那就再+1,看7行不行,直到找到结果。
发表于 2020-04-20 10:52:43 回复(0)
不难的题
tmp = [int(x) for x in input().split()]
m,n = tmp[0],tmp[1]
data = [int(x) for x in input().split()]
def ju(data,split_val):
    global n
    cur = 0
    cur_val = 0
    for i in data:
        cur_val+=i
        if cur_val>split_val:
            cur+=1
            cur_val=i
        if cur>=n:
            return False
    return True
lo = max(data)
hi = sum(data)
while lo<=hi:
    mid = (lo+hi)//2
    if ju(data,mid):
        hi = mid - 1
    else:
        lo = mid + 1
print(lo)
由于返回的是lo(st),所以达到要求就动hi(en),这样lo就一定是满足要求的,且是满足要求的最边界的z最大的切分数字,此时切成的数量最小。
初始是一块,每切一下多一块,所以
if cur>=n:
    return False
带着等号。

发表于 2019-11-06 22:16:17 回复(0)
LeetCode 410原题
发表于 2019-10-26 23:37:04 回复(0)
importjava.util.Scanner;
publicclassMain {
    publicstaticvoidmain(String[] args) {
        Scanner n =newScanner(System.in);
        intnum1 = n.nextInt();//5
        intnum2 = n.nextInt();//3
        intnum3 =0;
        if(num1%num2 ==0){
            num3 = num1/num2;
        }else{
            num3 = num1/num2 +1;
        }
        Scanner n2 =newScanner(System.in);
        String[] s = n2.nextLine().split(" ");
        int[] mu =newint[num1];
        for(inti =0;i<num1;i++){
            mu[i] = Integer.parseInt(s[i]);
        }
        int[] minnum =newint[num2];
        inti1 =0;
        inti2 = i1 + num3;
        inttemp =0;
        for(inti =0;i<3;i++){
            if(i2 < num1){
                for(intj = i1;j<i2;j++){
                    temp += mu[j];
                }
                minnum[i] = temp;
                temp =0;
                i1 = i2;
                i2 = i1 + num3;
            }else{
                temp =0;
                for(intk = i1;k < num1;k++){
                    temp += mu[k];
                }
                minnum[i] = temp;
            }
 
        }
        intminnumber =0;
        for(inti =0;i<num2;i++){
             
            for(intj = i+1;j<num2;j++){
                if(minnum[i]<=minnum[j]){
                    minnumber = minnum[i];
                }else{
                    minnumber = minnum[j];
                }
            }
        }
        System.out.print(minnumber);
    }
}
发表于 2019-09-06 00:34:24 回复(1)
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)

发表于 2019-08-22 17:11:06 回复(0)