首页 > 试题广场 >

Shopee的零食柜

[编程题]Shopee的零食柜

热度指数：5679 时间限制：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

输出

算法知识视频讲解

Java

牛客228437268号

看了一下大佬们在讨论区的解答，这道题的直观理解是按相邻数字和的最小值合并相邻数字，直到数字个数等于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)