首页 > 试题广场 > Shopee的零食柜
[编程题]Shopee的零食柜

        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

说明

6 | 5 6 | 7 | 6 | 6 3 1  为最优解

如果小于11,必然分段大于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)
#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)

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

发表于 2019-06-19 19:17:42 回复(2)
在总步长一定的情况下,步长和步数成反比例关系。所以,当步长最大为Sum,此时步数为1,当步长最小为Max,此时步数为n。所以为可以转化为,在Max和Sum中查找一个步长,该步长能使得步数小于等于m。
发表于 2019-07-06 16:09:02 回复(2)
自认为可读性更好些。
同样不明白为什么不是输出l。
#include<bits/stdc++.h>
using namespace std;
 
bool isOk(vector<int>& s, int step, int M){
    int cnt = 0;
    int tmpStep = 0;
    for(int i = 0; i < s.size(); i++){
        tmpStep += s[i];
        if(tmpStep > step){
            tmpStep = s[i];
            cnt++;
        }
        if(cnt > M){
            return false;
        }
    }
    if(tmpStep > 0 && cnt + 1 > M){
        return false;
    }
    return true;
}
 
int main(){
    int N, M;
    ios::sync_with_stdio(false);
    cin >> N >> M;
    vector<int> s(N);
    int max = 0;
    int sum = 0;
    for(int i = 0; i < N; i++){
        cin >> s[i];
        if(max < s[i]){
            max = s[i];
        }
        sum += s[i];
    }
    int l = max;
    int r = sum;
    int mid;
    while(l <= r){
        mid = l + ((r - l) >> 1);
        if(isOk(s, mid, M)){
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    cout << mid << endl;
 
    return 0;
}


发表于 2019-08-09 22:41:13 回复(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)

一个复杂度过高的DP算法

#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> rhythm(n);
    for (int i = 0; i < n; i++)
        cin >> rhythm[i];
    vector<int> dp(n, 0);
    vector<int> accu(n, 0);
    accu[0] = rhythm[0];  // 前缀和,用dp[m][n]会memory limit exceed
    for (int i = 1; i < n; i++)
        accu[i] = accu[i-1] + rhythm[i];
    for (int i = 0; i < n; i++)
        dp[i] = accu[i];
    for (int i = 1; i < m; i++)
        for (int j = n-1; j >= 0; j--) {
            int minmax = INT_MAX;
            for (int k = j-1; k >= 0; k--) {
                int maxlen = max(accu[j] - accu[k], dp[k]);  // 前k为一组, k-j为共i-1组
                minmax = min(maxlen, minmax);
            }
            dp[j] = minmax;
        }
    cout << dp[n-1] << endl;
    return 0;
}
编辑于 2019-07-30 11:52:55 回复(0)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int n, m;
int a[MAXN];
bool check(int x) {
    int sum = 0, ans = 0;
    for(int i=0; i<n; i++) {
        if(ans+a[i] > x) {
            sum++;
            ans = 0;
        }
        ans += a[i];
    }
    return sum < m;
}

int main() {
    cin>>n>>m;
    int l = 1, r = 0, m = 0;
    for(int i=0; i<n; i++) {
        cin>>a[i];
        r += a[i];
        l = max(l, a[i]);
    }
    while(l < r) {
        m = (l+r)/2;
        if(check(m)) r = m;
        else l = m+1;
    }
    cout<<r<<endl;
    return 0;
}
我觉得数据有问题!!!
发表于 2019-07-29 10:32:34 回复(0)
代码的可读性太差了,能不能解释一下关键代码?
发表于 2019-07-24 21:36:13 回复(0)
12 6
6 5 6 7 6 6 3 1 3 4 2 1
此样例输出应为11 结果为10还通过了只能说明题有问题
发表于 2019-07-24 12:11:11 回复(0)
题目都读不懂,到底要求啥😵😵😵
发表于 2019-07-16 20:49:11 回复(2)
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

class Solution{
    //存结果
    private ArrayList<ArrayList<Integer>>res=new ArrayList<>();

    public ArrayList<ArrayList<Integer>> getRes(ArrayList<Integer> nums,int m){
        ArrayList<Integer> list=new ArrayList<>();
        dfs(nums,list,0,0,m);
        return res;
    }

    //dfs
    public void dfs(ArrayList<Integer> nums,ArrayList<Integer> list,int cur,int num,int m){
        if(num==m&&cur==nums.size()){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i=cur;i<nums.size();i++){
            List<Integer> tmp=nums.subList(cur,i+1);
            list.add(sum(tmp));
            dfs(nums,list,i+1,num+1,m);
            list.remove(list.size()-1);
        }
    }
    
    //求和
    public int sum(List<Integer> nums){
        int res=0;
        for(Integer i:nums){
            res+=i;
        }
        return res;
    }
}
public class Main {

    public static void main(String[] args)throws IOException {
        Scanner sc=new Scanner(System.in);
        //Scanner sc=new Scanner(new File("/home/mao/workspace/java/src/WangNianZhenTI/Shoppe_02"));
        while (sc.hasNext()){
            int n=sc.nextInt();
            int m=sc.nextInt();
            ArrayList<Integer>nums=new ArrayList<>();
            for(int i=0;i<n;i++){
                nums.add(sc.nextInt());
            }
            if(n<=m){
                System.out.println(Collections.max(nums));
                return;
            }
            Solution solution=new Solution();
            ArrayList<ArrayList<Integer>> res=solution.getRes(nums,m);
            ArrayList<Integer> ans=new ArrayList<>();
            for(ArrayList<Integer> r:res){
                int tmp= Collections.max(r);
                ans.add(tmp);
            }
            System.out.println(Collections.min(ans));
        }
    }
}
难道是测试用例的问题?
发表于 2019-07-11 16:49:17 回复(1)

会超时,算法应该没问题。我再想想有啥可优化的么

/* 每次选择相邻两个数之和最小的两个数,删除这两个数,并用和代替这两个数,直到数据的规模和m相同 */
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

class solution
{
private:
    int n,m;
    std::vector<int> music_symbols;
public:
    solution();
    void input_data();
    void merge();

    /*  返回之和最小的相邻的两个数的前一个数的位置
        调用该函数必须保证 n > 1
    */
    std::vector<int>::iterator min_sum_position();
    void add_delete(std::vector<int>::iterator & min_position);
    // 返回 music_symbols 中的最大元素
    int max();
    ~solution();
};

solution::solution()
{
    input_data();
    merge();
    std::cout << max();
}

solution::~solution(){}

void solution::input_data()
{
    std::cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int temp;
        std::cin >> temp;
        music_symbols.push_back(temp);
    }
}

std::vector<int>::iterator solution::min_sum_position()
{
   std::vector<int>::iterator ret = music_symbols.begin();
   int min_sum = *ret + *(ret + 1);
   for (auto i = music_symbols.begin(); i != (music_symbols.end()-1); i++)
   {
       int sum = *i + *(i+1);
       if (sum < min_sum)
       {
           min_sum = sum;
           ret = i;
       }
   }

    return ret;
}

void solution::merge() 
{
    int count = n-m;
    for (int i = 0; i < count; i++)
    {
        auto min_position = min_sum_position();
        add_delete(min_position);
    }
}

void solution::add_delete(std::vector<int>::iterator & min_position)
{
    int sum = *min_position + *(min_position+1);
    (*min_position) = sum;
    music_symbols.erase(min_position+1);
}

int solution::max()
{
    return *std::max_element(music_symbols.begin(), music_symbols.end());
}

int main(int argv, char **argc)
{
    solution s;
    return 0;
}
编辑于 2019-07-03 16:15:21 回复(0)
这题测试用例有问题?
发表于 2019-06-15 09:21:45 回复(6)