Shopee的零食柜

测试样例？n为100000，结果下面只有3578个数据？这怎么跑得出结果

/*
    如果一分钟跑完则每分钟最多跑序列的总和步 right
    如果n分钟跑完则每分钟最多跑序列中最大数的步数 left
    问题转换为在[left, right]中找到一个左边界数，使得步数最小又能在规定的时间内跑完
*/
#include<bits/stdc++.h>
using namespace std;
void Core(int left, int right, int n, int m, vector<int> vec)
{
    int mid = left+(right-left)/2;
    while(left <= right)
    {
        mid = left+(right-left)/2;
    
        int num = 0;
        for(int k = 0; k < n;)
        {
            int sum = 0;
            //既要满足步数小于某个数
            while(k < n && sum + vec[k] <= mid) sum += vec[k++];
            num++;
            //又要满足分钟数内跑完
            if(num > m) break;
        }
        if(num > m) left = mid+1;
        else right = mid -1;
    }
    cout << mid << endl;
}
int main()
{
    int n,m;cin >>n >>m;
    vector<int> vec(n,0);
    int left = 0;
    int right = 0;
    for(int i = 0; i < n;i++)
    {
        cin >> vec[i];
        right += vec[i];
        left = max(left, vec[i]);
    }
    Core(left, right, n, m, vec);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //数组中的最大值
        int min = 0;
        //数组所有值总和
        int max = 0;
        Scanner sc = new Scanner(System.in);
        int musicSize = sc.nextInt();
        int run = sc.nextInt();
        int[] music = new int[musicSize];
        for (int i = 0; i < music.length; i++) {
            int mus = sc.nextInt();
            music[i] = mus;
            min = Math.max(min, mus);
            max += mus;
        }
        while(min < max) {
            //求出min和max的平均数
            int result = (max + min)>>1;
            int sum = 0;
            //模拟的分钟数
            int index = 1;
            for (int i = 0; i < music.length; i++) {
                //如果数组的元素小于平均数，赋值给sum，直到sum的值大于平均值时，模拟的分钟数+1；
                if (sum+music[i] <= result){
                    sum=sum+music[i];
                }else {
                    sum =music[i];
                    index++;
                }
            }
            //如果模拟的分钟数超过输入的时间，加快min直到min>=max；
            if (index>run){
                min=result+1;
            //如果模拟的分钟数小于输入的时间，减慢max直到min>=max；
            }else if (index<run){
                max=result-1;
            //如果模拟的分钟数等于输入的时间，让max等于平均数直到min>=max
            }else {
                max = result;
            }
        }
        System.out.println(min);
    }
}

GoLang版本，提示运行超时，通过率14.29%，此解法时间复杂度太高，修改中。

package main
import "fmt"
func main(){
    var n,m int
    _,_ = fmt.Scanln(&n,&m)
    var nums []int
    for i:=0;i<n;i++{
        var t int
        _,_ = fmt.Scan(&t)
        nums =append(nums,t)
    }
    fmt.Println(getMinSub(m,nums))
}
func getMaxInt(arr []int) int {
    result := arr[0]
    for _,v := range arr {
        if result  < v {
            result = v
        }
    }
    return result
}
func getMinSub(m int, arr []int) int {
    var minIndex int
    for len(arr)!=m {
        minSum := arr[0]+arr[1]+1
        for i:=0; i<len(arr)-1; i++{
            if minSum>arr[i]+arr[i+1]{
                minSum = arr[i]+arr[i+1]
                minIndex = i
            }
        }
        arr[minIndex] = minSum
        arr = append(arr[:minIndex+1],arr[minIndex+2:]...)
    }
    return getMaxInt(arr)
}

新版本，通过所有测试用例

package main

import "fmt"

func main(){
    var n,m int    //n为数组长度，m为最大限制时间
    _,_ = fmt.Scanln(&n,&m)    // 以回车结束输入
    var nums []int
    var sums int
    var maxInt int
    for i:=0;i<n;i++{
        var t int
        _,_ = fmt.Scan(&t)    // 以空格结束输入
        nums =append(nums,t)
        sums+=t               // 累计数组总和
        if(maxInt<t){
            maxInt=t          // 求数组中最大值元素
        }
    }
    fmt.Println(bisection(nums,n,m,maxInt,sums))
}

// 检查输入的步长是否符合规定
func check(arr []int, test int, m int) int {
    sum := 0 // 前K项累加和
    num := 1 // 时间计数
    for i:=0; i<len(arr); i++{
        if sum+arr[i] <= test{
            sum+=arr[i]
        }else{
            sum = arr[i]
            num++
        }
    }
    if num<m{            // 实际消耗时间低于给定时间，即步长偏大
        return -1
    }else if num>m{      // 实际消耗时间高于给定时间，即步长偏小
        return 1
    }else{               // 实际消耗时间等于给定时间，即步长合适，但不一定是最小步长
        return 0
    }
}

// 二分法
func bisection(arr []int, n int, m int,left int, right int) int{
    // 循环条件，左边界小于右边界
    for left < right{
        mid := (left+right)>>1    // 右移1位，即除以2
        cmp := check(arr,mid,m)   // 检测设计步长是否合规
        if cmp == -1{
            right = mid -1        // 步长过高，需减小
        }else if cmp == 1{
            left = mid +1         // 步长过低，需增大
        }else{
            right = mid           // 步长合适，但不一定会退出循环
        }
    }
    return left
}

//二分答案
//关键是确定二分的上下界
//当m=1时，所有步数总和为上界
//当m=n时，步数的最大值为下界
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6;

int a[MAXN+5];
int n,m;

void bSearch(int lower,int upper){
    int mid;
    while(lower<=upper){
        mid = (lower+upper)>>1;
        int curSum = 0;
        int cnt = 0;
        bool flag = 1;
        for(int i=0;i<n;){
            while(i<n&&curSum+a[i]<=mid) curSum+=a[i++];
            cnt++;
            //不满足提前退出
            if(cnt>m) { flag = 0;break;}
            curSum = 0;
        }
        //满足说明可以进一步缩小
        if(flag) upper = mid-1;
        else lower = mid+1;
    }
    printf("%d\n",mid);
}

int main() {
    while(~scanf("%d%d",&n,&m)){
        int MAX = 0 ,sum = 0;
        for(int i=0;i<n;i++) {
            scanf("%d", &a[i]);
            MAX = max(MAX, a[i]);
            sum += a[i];
        }
        bSearch(MAX,sum);
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool judge(const int& stepLen, const vector<int>& num, int steps) {
    int tempSum = 0, cur = 0, i = 0, len = num.size();
    for (i = 0; i < len; ++i) {
        tempSum += num[i];
        if (tempSum > stepLen) {
            cur++;
            tempSum = num[i];
        }
        if (cur >= steps)
            break;
    }
    return i == len;
}
int main() {
    int n, m;
    cin >> n >> m;
    if (n <= 0)
        return 0;
    vector<int> num;
    int maxNum = 0, sumNum = 0, temp;
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        num.push_back(temp);
        maxNum = max(maxNum, temp);
        sumNum += temp;
    }
    int left = maxNum, right = sumNum, ans = right, mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (judge(mid, num, m)) {
            right = mid - 1;
            ans = min(ans, mid);
        }
        else
            left = mid + 1;
    }
    cout << mid << endl;  //cout<<ans<<endl通过率只有50%
    return 0;
}

不明白为什么最后输出mid而不是ans

/*
这个题目的实际含义就是：
（1）把一个长度为n的数组，顺序不变的情况下划分为m个子数组，可以理解为长度为n的数组中插入m-1个split
（2）在所有划分方案中，找到一种方案使得m个子数组中的和最大的子数组的和尽可能的小
*/

#include <vector>
#include <iostream>

using namespace std;

void split(vector<int>& v, int n, int m, int l, int r){
    int mid = 0;
    int last = 0;
    while(l <= r){
        mid = (l+r) / 2;
        int cnt = 0;
        for(int i=0;i<n;){
            int sum = 0;
            while(i < n && sum + v[i] <= mid){
                sum += v[i];
                i++;
            }
            cnt ++;
            if(cnt > m){
                break;
            }
        }
        if(cnt > m){
            l = mid + 1;
        }
        else{
            last = mid;    //记录最后一次符合题意的mid
            r = mid - 1;
        }
    }
    cout << last << endl;
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    int max = 0;
    int sum = 0;
    for(int i=0;i<n;i++){
        cin >> v[i];
        if(v[i] > max){
            max = v[i];
        }
        sum += v[i];
    }
    //输出的数字一定是[max, sum]之间的
    //当m==n的时候，每个子数组一个值，子数组和最大就是max
    //当1==m的时候，整个数组分为一个子数组，子数组和最大就是sum
    split(v, n, m, max, sum);
    return 0;
}

//只通过42%的测试case

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> steps(n,0);
      int sum = 0;
        int maxStep = 0;
        vector<int> preSum(n,0);
        for(int i = 0; i < n; i++) {
            cin >> steps[i];
            sum += steps[i];
            maxStep = max(maxStep, steps[i]);
            preSum[i] = sum;
        }

        int res = sum;
        int count = 0;
        int lastSum = 0;
        int lastCount = -1;
        int aver = (sum%m == 0)? sum/m : sum/m + 1;
        int init = (sum/maxStep > m)? sum/maxStep : maxStep;
        int lastPreSumIdx = 0;
        for(int sp = aver; sp <= sum; sp++) {
            count = 0;
            lastSum = 0;
            for(int i = lastPreSumIdx+1; i < n; ) {
                if(preSum[i] - lastSum <= sp) {
                    i++;
                }
                else {
                    count++;
                    lastSum = preSum[i-1];
                    if(lastSum == 0) {
                        lastPreSumIdx = i-1; //优化时间
                    }
                    if(count > m) {
                        break;
                    }
                }
            }
            if(count > m) continue;
            //if(count < m && sum - lastSum < sp) count++;
            if(count <= m) {
                res = sp;
                cout << res << endl;
                break;
            }
        }
}

#include <iostream>
#include <vector>
#include <numeric>
#include <limits>
#include <algorithm>

using namespace std;
    bool check(vector<int>& nums, int x, int m) {
        long long sum = 0;
        int cnt = 1;
        for (int i = 0; i < nums.size(); i++) {
            if (sum + nums[i] > x) {
                cnt++;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
        }
        return cnt <= m;
    }

    int splitArray(vector<int>& nums, int m) {
        long long left = 0, right = 0;
        for (int i = 0; i < nums.size(); i++) {
            right += nums[i];
            if (left < nums[i]) {
                left = nums[i];
            }
        }
        while (left < right) {
            long long mid = (left + right) >> 1;
            if (check(nums, mid, m)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> nums(n,0);
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cout << splitArray(nums, m) << endl;
}