首页 > 试题广场 >

Shopee的零食柜

[编程题]Shopee的零食柜
  • 热度指数:5676 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

        shopee的零食柜,有着各式各样的零食,但是因为贪吃,小虾同学体重日益增加,终于被人叫为小胖了,他终于下定决心减肥了,他决定每天晚上去操场跑两圈,但是跑步太累人了,他想转移注意力,忘记痛苦,正在听着音乐的他,突然有个想法,他想跟着音乐的节奏来跑步,音乐有7种音符,对应的是1到7,那么他对应的步长就可以是1-7分米,这样的话他就可以转移注意力了,但是他想保持自己跑步的速度,在规定时间m分钟跑完。为了避免被累死,他需要规划他每分钟需要跑过的音符,这些音符的步长总和要尽量小。下面是小虾同学听的歌曲的音符,以及规定的时间,你能告诉他每分钟他应该跑多少步长?



输入描述:
输入的第一行输入 n(1 ≤ n ≤ 1000000,表示音符数),m(1<=m< 1000000, m <= n)组成,

第二行有 n 个数,表示每个音符(1<= f <= 7)


输出描述:
输出每分钟应该跑的步长
示例1

输入

8 5 6 5 6 7 6 6 3 1

输出

11
首先说下结果,自测结果通过,但提交结果运行超时,case通过率14.29%。说明思路基本正确,但是代码需要改进,代码的时间复杂度O(N^2)。
刚看时不懂题在说什么,后面看大家的讨论有点懂问题是什么。用自己的话说下,输入是这样:
8 5 6 5 6 7 6 6 3 1
第一个元素8是后面数据长度。第二个元素5是要求最后的数据长度。第三个以及之后的组成需要处理的数据。也就是 
6 5 6 7 6 6 3 1
是数据。共8个元素,要把这8个元素变为5个,但是总和不能变,每次个数-1时,合并相邻元素之和最小的数。也就是当8个元素变成7个时,相邻元素和最小的是最后的2个,所以3与1相加为4,加入链表中,而之前的3,1被删掉了,合并后会成为下面的数据:
6 5 6 7 6 6 4
然后之后的就是6和4:
6 5 6 7 6 10
之后6和5:
11 6 7 6 10
此时数据元素为要求的5个,所以合并接受,要求的结果就是这组数据中最大的那个。那就是11。返回11就是结果了。
Java的实现代码如下
import java.util.ArrayList;
import java.util.Scanner;

class Solution {
    public int getMinStep(int n, int m, ArrayList<Integer> arr) {
        int minIndex1 = 0;
        int minIndex2 = 1;
        int minSum;
        while (arr.size() != m) {
            minSum = Integer.MAX_VALUE;
            for (int i = 0, j = i + 1; i < arr.size() - 1 && j < arr.size(); i++, j++) {
                if (minSum > arr.get(i) + arr.get(j)) {
                    minSum = arr.get(i) + arr.get(j);
                    minIndex1 = i;
                    minIndex2 = j;
                }

            }
            arr.set(minIndex1, minSum);
            arr.remove(minIndex2);

            /*for (int i = 0; i < arr.size(); i++) {
                System.out.print(arr.get(i) + " ");
            }
            System.out.println(minSum+"_");*/
        }
        int result = this.getMaxInt(arr, n);
        return result;
    }

    public int getMaxInt(ArrayList<Integer> arr, int n) {
        int result = arr.get(0);
        for (int i = 0; i < arr.size(); i++) {
            if (result < arr.get(i)) {
                result = arr.get(i);
            }
        }
        return result;
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arr.add(sc.nextInt());
        }
        /*for (int i = 0; i < n; i++) {
            System.out.println(arr[i]);
        }*/
        //完成初始数据采集
        Solution solution = new Solution();
        int result = solution.getMinStep(n, m, arr);
        System.out.println(result);
    }
}

























发表于 2020-02-08 21:48:59 回复(1)

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

发表于 2019-06-19 19:17:42 回复(3)
import java.util.Scanner;
 
public class Main {
  
       public static void main(String[] args) {
         Scanner scanner = new Scanner(System.in);
         int n = scanner.nextInt();
         int m = scanner.nextInt();
         int[] arr = new int[n];
         int left = Integer.MIN_VALUE;
         int right = 0;
         for(int i =0 ; i < n ; i++) {
             arr[i] = scanner.nextInt();
             left = Math.max(left, arr[i]);
             right += arr[i];
         }
         while(left < right) {
             int midlle = (left + right)>>1;
             int cmp = check(arr,midlle,m);
             if(cmp==-1) {
                 right = midlle-1;
             }else if(cmp==1){
                 left = midlle + 1;
             }else{
                 right=midlle;
             }
         }
          
         System.out.println(left);
         scanner.close();
       }

       private static int check(int[] arr,int test,int m){
            int sum = 0;
            int num = 1;
            for(int i = 0; i < arr.length ; i++) {
                if(sum + arr[i]<=test) {
                    sum += arr[i];
                }else {
                    sum = arr[i];
                    num ++;
                }  
            }
            return num<m?-1:(num>m)?1:0;
       }
}
发表于 2020-02-13 13:13:27 回复(5)
C++抄的前面答案的
/*
    如果一分钟跑完则每分钟最多跑序列的总和步 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;
}

发表于 2019-08-04 16:38:11 回复(1)
发表于 2020-08-27 21:17:31 回复(1)
这出的什么破题啊,题目描述不清,用例也有问题,浪费时间,吐了。建议大家不要做
以下是根据评论区通过的代码修改后的结果,满满的问号
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
    int n, m, sum = 0;
    cin >> n >> m;
    vector<int> step(n);
    //最小值=最大步长,最大值=最大步长*每分钟平均听的音符数
    int min = 0, max = 0;
    for(int i = 0; i<n; ++i){
        cin >> step[i];
        if(min<step[i]) min = step[i];
        max += step[i];
    }
    //max=最大步长*平均每分钟所听音符数ceil(n*1.0/m)有问题吗?不比求和要好?
    //max=min*ceil(n*1.0/m);
    int mid, cost, temp;
    //以最大最小值为上下区间,二分法求解
    while(min<max){
        mid = (max+min)>>1;
        cost = 1;
        temp = 0;
        for(int i = 0; i<n; ++i){
            if(temp+step[i]<=mid) {
                temp+=step[i];
            }
            else{
                temp = step[i];
                ++cost;
            }
        }
        //cost时间小于等于m时,表示当前mid满足时间要求,但不一定是最小mid;保留此结果到下一半
        //if(cost<=m){
        //    max = mid;
        //}
        if(cost==m){
            max = mid;
        }
        else if(cost<m){
            max = mid - 1;
        }
        else {
            min = mid + 1;
        }
    }
    //返回右界不行必须返回左界?
    cout << min << endl;
    return 0;
}


编辑于 2020-07-24 20:34:03 回复(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);
    }
}

发表于 2020-07-21 13:10:50 回复(0)

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
}
编辑于 2020-07-23 10:20:21 回复(0)
看了一下大佬们在讨论区的解答,这道题的直观理解是按相邻数字和的最小值合并相邻数字,直到数字个数等于m,输出最大的数。但是按照这个理解写的算法,复杂度好像太大了不合题意。再看了看通过的代码,其实用了动态规划算法,整个数组(音符组)nums[n],最少1分钟跑完这些音符,即最大步数为该数组的和;
若2分钟跑完,最大步数应为数组最大值max+(数组的总和sum-数组最大值max)/2,(可以理解为数组的对半求和);
判断按照当前最大步数steps跑,需要跑多少分钟times,若times大于m(跑得太慢),说明当前最大步数steps太小了,需要增大最大步数;若times小于m(跑得太快),说明当前最大步数max太大了,需要减小步数。按照对半求和继续算步数。
(还有,我本来用BufferedReader和InputStream来接收输入数据,但题目说运行时间太大,改用Scanner可以了)
import java.util.Scanner;

public class Main{
    public static int timeCheck(int[] a,int step){
        int time=1;//最少也要一分钟
        int sum=0;//前k步步数总和
        for(int i:a){
            if(sum+i>step){//前k步步数和大于step(最大步数)
                sum=i;
                time+=1;
            }else{
                sum+=i;
            }
        }
        return time;
    }
    public static void main(String args[]) throws IOException{
        Scanner bf=new Scanner(System.in);
        int max=0;
        int sum=0;
        int steps=0;
        int times=0;
        int n=bf.nextInt();
        int m=bf.nextInt();
        int a[]=new int[n];
        for(int i=0;i<n;i++){
            a[i]=bf.nextInt();
            max=Math.max(max,a[i]);
            sum+=a[i];
        }
        while(max<sum){
            steps=max+(sum-max)/2;
            times=timeCheck(a,steps);
            if(times>m){//花费时间大于规定时间 m,故最大步数要增大
                max=steps+1;
            }else if(times<m){//花费时间小于规定时间 m,故最大步数要减少
                sum=steps-1;
            }else{//花费时间等于规定时间,比较最大步数和总和的大小
                sum=steps;
            }
        }
        System.out.println(max);
        bf.close();
    }
}


编辑于 2020-06-10 21:05:17 回复(2)
一开始没有读懂题目,后来参考了几个大佬的代码明白了题意
输入的n是脚步的数量,m是分钟,一分钟可以走多个脚步,也就是极端情况下一分钟走完所有脚步,m=1,此时步长就是n个脚步和,另一个极端情况就是每次只走一个脚步,样例中最大的脚步是7,所有极端是每次可以走7,走小于7也是可以的,即每分钟一个脚步,用了8分钟,样例中输入了m=5,8>5,显然是不合理的,所以才需要我们去找一个合理的步长,一个步长至少包含一个脚步长度。
如果用二分查找就是在脚步最大值max和全部脚步和sum中查找一个合适的步长mid使得走的时间小于5并且这个步长还是最小的。
算法如下,代码没有过测试,仅供参考
class Main {
    public void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String temp = sc.nextLine();
        String[] str = temp.split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        int[] arr = new int[n];
        int j = 2;
        int max = 0;
        int sum = 0;
        for(int i = 0; i < n; i++) {
            arr[i] = str[j++];
            sum += arr[i];
            if(arr[i] > max) 
                max = arr[i];
        }
        int res = 0;
        res = b_search(max, sum);
        return res;
    }
    
    public int b_search(int max, int sum) {
        int left = max;
        int right = sum;
        int cur_sum = 0;
        int count = 0;
        boolean flag = true;
        while(left <= right) {
            mid = left + (right-left)/2;
            for(int i = 0; i < n; ) {
                while(i < n && cur_sum + arr[i] <= mid) {
                    cur_sum += arr[i];
                    i++;
                }
                count++;
                if(count > m) {
                    flag = false;
                    break;
                }
            }
            if(flag == true) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            cur_sum = 0;
            count = 0;
        }
        return left;
    }
    
}


发表于 2019-10-25 16:30:20 回复(0)
//二分答案
//关键是确定二分的上下界
//当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;
}
发表于 2019-08-02 16:00:50 回复(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

发表于 2019-07-24 22:06:08 回复(3)
在总步长一定的情况下,步长和步数成反比例关系。所以,当步长最大为Sum,此时步数为1,当步长最小为Max,此时步数为n。所以为可以转化为,在Max和Sum中查找一个步长,该步长能使得步数小于等于m。
发表于 2019-07-06 16:09:02 回复(2)
谁来解释下 到底什么意思  读不懂题目

发表于 2019-09-12 18:15:22 回复(6)
/*
这个题目的实际含义就是:
(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;
}
虽然没有通过所有测试用例,但是我相信肯定是测试用例不对!
发表于 2019-09-13 15:25:55 回复(7)
O(n^2)的时间复杂度都超时了,还有O(n)的时间复杂度算法吗?求分享
importjava.util.*;
publicclassMain{
    publicstaticvoidmain(String[] args){
        Scanner sc = newScanner(System.in);
        intn = sc.nextInt(), m = sc.nextInt();
        int[] a = newint[n];
        intans = 0;
        List<Integer> list = newArrayList();
        for(inti = 0; i < n; i++){
            list.add(sc.nextInt());
            ans = Math.max(ans, list.get(list.size() - 1));
        }
 
         
        for(inti = 0; i < n - m ; i++){
            intmin = list.get(0) + list.get(1);
            intindex = 0;
            for(intj = 1; j < list.size() - 1; j++){
                if(list.get(j) + list.get(j + 1) < min){
                    min = list.get(j) + list.get(j + 1);
                    index = j;
                }
            }
            ans = Math.max(min, ans);
            list.set(index, min);
            list.remove(index + 1);
        }
        System.out.println(ans);
    }
}

编辑于 2022-02-21 20:03:38 回复(0)
案例答案有错误,望更正。leetcode是可以通过的

发表于 2022-01-12 05:24:41 回复(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;
            }
        }
}

看了下Leetcode的
leetcode官方动态规划解答,在这题提交,超内存。
下面这二分法在这题提交,只能过52%的case,怀疑是后台测试case有误。
#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;
}


编辑于 2021-03-29 00:09:32 回复(1)
const m = 5;
let step = [6, 5, 6, 7, 6, 6, 3, 1];
const cutdown = step.length - m;
const combinelow = (source) => {
  let indexCache = [];
  let sumCache = [];
  for (let i = 0; i < source.length; i++) {
    if (i + 1 < source.length) {
      const current = source[i];
      const next = source[i + 1];
      const sum = current + next;
      indexCache[sum] = i; // start index of the sum
      sumCache = [...sumCache, sum];
    }
  }
  // find the start index of the minimum sum
  const minSum = Math.min(...sumCache);
  const startIndex = indexCache[minSum];
  source.splice(startIndex, 2, minSum);
  return source;
};

for (let i = 0; i < cutdown; i++) {
  step = combinelow(step);
}

console.log(Math.max(...step));


编辑于 2020-11-23 22:26:24 回复(0)
题目不太好理解,其实就是典型的最大最小值问题,二分探测就可以了。但是不知道为什么有个用例过不去,吐了。
发表于 2020-08-21 14:15:56 回复(0)

热门推荐

通过挑战的用户

查看代码