携程笔试任务调度那个题，用么做啊

lc410

Dp不会写，写了个最大数加最小数输出了个27%交了

leetcode 410 二分枚举 + 线性贪心检查是否能符合，时间复杂度O(nlog(sum)) class Solution { public:     bool canSplit(vector<int>& nums, int m, int mid){         // cout << mid << ' ';         long long sum = 0, cnt = 1;         for(int &x: nums){             if(sum + x > mid){                 sum = x;                 ++cnt;                 if(cnt > m) return false;             }else sum += x;         }         return true;     }     int splitArray(vector<int>& nums, int m) {         long long l = 0, r = 0;         for(int &x: nums){             r += x;             if(x > l) l = x;         }         while(l < r){             int mid = l + r >> 1;             // cout << l << ' ' << r << ' ' << mid << endl;             if(canSplit(nums, m, mid)) r = mid;             else l = mid + 1;         }         return r;     } };

leetcode 410 动态规划版本，dp[i][j]表示到i为止，分割为j组的最小最大和。 class Solution { public:     int splitArray(vector<int>& nums, int m) {         int n = nums.size();         vector<vector<long>> dp(n+1, vector<long>(m+1, ~(1<<31)));         vector<long> sums(n+1, 0);         // nums.push_front(0);         for(int i=1; i<=n; ++i) sums[i] = sums[i-1] + nums[i-1];         for(int i=0; i<=n; ++i) dp[i][1] = sums[i]; // 到i为止，只分一组。         for(int i=1; i<=n; ++i){             for(int j=1; j<=m; ++j){                 for(int k=0; k<=i; ++k){ // 枚举到i为止所有切割点。                     dp[i][j] = min(dp[i][j], max(dp[k][j-1], sums[i]-sums[k]));                 }             }         }         return dp[n][m];     } };

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Main {     /*请完成下面这个函数，实现题目要求的功能     当然，你也可以不按照下面这个模板来作答，完全按照自己的想法来 ^-^     ******************************开始写代码******************************/     static int[][] dp;          static int schedule(int m,int[] array) {         int len = array.length;         dp = new int[len][m+1];         dp[0][1] = array[0];         for (int i=1; i<len; i++){             dp[i][1] = dp[i-1][1] + array[i];         }         for (int i=0; i<len; i++){             for (int j=2; j<=m; j++){                 int maxValue = Integer.MAX_VALUE;                 for (int k=0; k<i; k++){                     maxValue = Math.min(maxValue, Math.max(dp[k][j-1], dp[i][1]-dp[k][1]));                 }                 dp[i][j] = maxValue;             }         }         return dp[len-1][m];     }          /******************************结束写代码******************************/     public static void main(String[] args){         Scanner in = new Scanner(System.in);         int m = in.nextInt();         int size  = in.nextInt();         int[] array = new int[size];         for(int i = 0; i < size; i++) {             array[i] = in.nextInt();         }         int res = schedule(m,array);         System.out.println(String.valueOf(res));     } }

二分做简单，leetcode410

A了70+ 我知道投机取巧不好，人工判卷，注释里写了检讨。

其实就是dp问题，数组n个值切割成m段，保证m段中和值最小，跟上次shopee笔试题《shopee的零食柜》一模一样。。。

看了半天不会做

二分答案基础题目

网上有几种解法，搜一下就出来了

就是数组分段求和

没有第二题的代码吗，司马一直57.。。

时间超时的我

求出每段的平均值，然后从头开始找连续段，尽量保证在平均值附近😂，也算是贪心吧，过了70%多

暴力过了100%，先算出数组最大元素max，然后判断为max时能否将数组分为进程n组，如果不能则max++，继续判断

感觉思路就是把数组中的时间全部加起来，然后充当最大值。找出数组中最大的那个时间，充当最小值。那么时间范围就确定了，此时就通过二分去找出答案。但不知道为什么才 77%，求解答

每次取数组然后分割成两半，前小，后大；然后取大继续分割，直到分割次数达到m……用优先队列 所以队头一定是范围最大的，后面时间来不及写。。不知道对不对

我是找了每个任务出现的最早和最晚时间， 然后区间合并， 复杂度有点高。。

还是不行啊！谁能做出来啊