首页 > 试题广场 >

探险安排

[编程题]探险安排
  • 热度指数：737 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

小明要为n个人计划一次火星的探险，其中一个重要的任务是为每个参与者安排食物。仓库里面有m个能用一天的食物包裹，每个食物包裹有不同的类型ai。

每个人每天必须用且只能用一个食物包裹。由于某些原因，在整个过程中，每个人只能用同一种类型的食物包裹，但是不同的人用的食物包裹可以不一样。

给出人数以及食物包裹的情况，请你求出这趟探险最多可以持续多少天。


输入描述:
第一行两个整数，n和m，表示人数和食物包裹的个数。
第二行m个整数，表示每个食物包裹的类型。
满足1 <= n <= 100,1 <= m <= 100,1 <= ai <= 100。


输出描述:
一个整数，表示最多持续的天数；如果一天都无法持续，输出0。
示例1

输入

4 10
1 5 2 1 1 1 2 5 7 2

输出

2
算法知识视频讲解
添加回答
npucfy头像 npucfy 
//二分答案
#include<bits/stdc++.h>
using namespace std;
 
int n,m,x;
unordered_map<int,int> um;
 
int check(int m) {
    int sum=0;
    for(auto i:um) {
        sum+=i.second/m;
    }
    return sum>=n;
}
 
int main() {
    cin>>n>>m;
    if (m<n) {cout<<0;return 0;}
    int l=1,r=m/n;
    for(int i=1;i<=m;i++) {
        cin>>x;
        um[x]++;
    }
    while (l<r) {
        int mid=(l+r)>>1;
        if (check(mid)) l=mid+1;
        else r=mid;
    }
    if (check(l)) cout<<l;
    else cout<<l-1;
    return 0;
}
比较简单的二分答案的思想
发表于 2020-03-14 14:11:11 回复(2)
codeNinja头像 codeNinja
抛砖引玉，不知道哪个边界条件没有考虑到 
const [numP, numF] = readline().split(' ').map(e => e*1),
      foods = readline().split(' ').map(e => e*1);

function main() {
    let q=[];
    for(let i=0; i<numF; ++i){
        if(q[foods[i]] === undefined){
            q[foods[i]] = 1;
        }else{
            q[foods[i]] = q[foods[i]] + 1;
        }
    }

    q = q.filter(e => e!==undefined);
    const dp = Array(numP+1).fill().map(_ => Array(q.length+1).fill());

    for(let i=0; i<=q.length; ++i){
        for(let j=0; j<=numP; ++j){

            if(j===0){
                dp[j][i] = Number.POSITIVE_INFINITY;
            }else if(i === 0){
                dp[j][i] = 0;
            }else{
                dp[j][i] = Number.NEGATIVE_INFINITY;
                let temp;
                for(let k=0; k<=j; ++k){
                    if(k===0){
                        dp[j][i] = dp[j][i] > dp[j][i-1] ? dp[j][i] : dp[j][i-1];
                    }else{
                        temp = Math.min(Math.floor(q[i-1]/k), dp[j-k][i-1]);
                        dp[j][i] = dp[j][i] > temp ? dp[j][i] : temp;
                    }
                }
            }
        }
    }
    
    print(dp[numP][q.length]);
}

main();


您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为90.00%
用例:
5 79
88 36 16 64 38
76 18 98 51 7 30 27 83 41 38 33 17 13 46 73 39 41 72 84 79 42 2 6 1 16 68 22 86 45 76 41 82 83 81 74 36 27 82 32 96 74 85 88 25 24 54 70 54 55 38 62 29 62 21 100 38 9 33 79 18 44 8 57 51 6 64 44 80 52 63 50 56 18 37
对应输出应该为:
2
你的输出为:
1
发表于 2020-03-14 12:35:02 回复(1)
清举头像 清举 
let [n, m] = readline().split(' ').map(e => e * 1),
    arr = readline().split(' ').map(e => e * 1);
if (arr.length < m) {
    arr = arr.concat(readline().split(' ').map(e => e * 1));
}
function fn1(n, m, arr1) {
    if (n > m) {
        console.log(0);
    } else if (m < 2 * n) {
        console.log(1);
    } else {
        var arr1 = arr.slice(0, n);
        var arr2 = [];
        for (var i = 0; i < arr1.length; i++) {
            var count = 0;
            for (var j = n; j < arr.length; j++) {
                if (arr1[i] == arr[j]) {
                    count++;
                }
            }
            arr2.push(count);
        }
        arr2.sort();
        console.log(arr2[0] + 1);
    }
}
fn1(n, m, arr);

编辑于 2020-10-12 01:56:21 回复(0)
还哈头像 还哈
#include <stdio.h>
int main()
{
    int n,m;
    scanf("%d",&n);
    scanf("%d",&m);
    int a[m],i=0,j=1,x=0,c[100][2],f=0,k=0;
    while(i<m)
    {
        scanf("%d",&a[i]);
        i++;
    }
    while(j<101){
    while(x<m)
    {
        if(j==a[x])
            f++;
    x++;}
    x=0;
    if(f!=0)
    {c[k][0]=a[x];
        c[k][1]=f;
            k++;
    }
    j++;
        f=0;
}
    int s,t=0,l,o=0;
    s=m/n;
      
    while(1){
        if(s==0)
            {printf("%d",s);
        break; }
      
    for(int v=0;v<k;v++)
    {
        if(c[v][1]>=s)
           t=c[v][1]/s+t;
          
          
    }
        l=t;
        t=0;   
    if(l>n){
          
    if(o==0)   
    s++;
    if(o!=0)
    {printf("%d",s);
        break; }
    }
    if(l==n){
        printf("%d",s);
        break;
    }
    if(l<n)
    {s--;
     o++;
    }
    }
}
发表于 2020-10-10 23:44:56 回复(0)
offer快到碗里来呀~头像 offer快到碗里来呀~ 
#include<iostream>
(720)#include<vector>
#include<algorithm>
using namespace std;
 
int main(){
    int n=0;
    int m=0;
    cin>>n>>m;
    vector<int> a;
    int k=0;
    for(int i=0;i<m;i++){
        cin>>k;
        a.push_back(k);
    }
    sort(a.begin(),a.end());
    int l[100]={0};
    for(int i=0;i<a.size();i++){
        l[a[i]]++;
    }
    sort(l,l+100);
    vector<int> h;
    for(int j=0;j<100;j++){
        if(l[j]>0)
        {
            h.push_back(l[j]);
        }
    }
    //最多的天数
    int g=m/n;
    int c=h.size()-1;
    int b=0;
    int flag=0;
    int d=n;
    for(int j=g;j>0;j--){
        for(int c=h.size()-1;c>=0;c--){
        b=h[c]/j;
        d=d-b;
        if(d<=0){
            cout<<j<<endl;
            flag=1;
            break;
        }
        }
        if(flag==1){
            break;
        }else{
            d=n;
        }
    }
    if(flag==0){
    cout<<'0'<<endl;}
    return 0;
}

发表于 2020-04-06 21:33:46 回复(0)
提交观点

问题信息

前端工程师 2019 百度
上传者：小小
难度：
5条回答 3644浏览

热门推荐

通过挑战的用户

相关试题

探险安排

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号