我要招人

去企业版

首页 > 试题广场 >

能吃几份

[编程题]能吃几份

热度指数：135 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

牛牛参加了大胃王比赛，面前摆上了 $\mathit n$ 道美食，若已知每道美食能够提供的饱腹感以及牛牛感到吃撑时的饱腹感至少需要多少，那么，牛牛最少吃几份能够吃撑自己，请告诉他一种吃美食方案。

输入描述:

本题为多组测试数据，第一行输入一个正整数 ，代表测试数据组数。

对于每组测试数据，第一行输入两个正整数 ，代表美食数量以及牛牛感到吃撑时的饱腹感。
第二行输入  个数，依次代表每道美食所能共提供的饱腹感，每道美食能提供的饱腹感不会超过 .

输出描述:

对于每组测试数据，如果这些美食能够让牛牛吃撑，那么请在第一行输出牛牛最少吃几份能吃撑，在第二行输出对应的吃美食方案，若存在多种方案，则任意输出一种即可；如果这些美食不能让牛牛吃撑，那么只需要在一行输出  即可。

示例1

输入

输出

2
1 3
-1

算法知识视频讲解

牛客252064727号

贴一个自己写的，新手勿喷。。。

const rl = require("readline").createInterface({ input: process.stdin });

var iter = rl[Symbol.asyncIterator]();

const readline = async () => (await iter.next()).value;

let input = [];

void (async function () {

// Write your code here

while ((line = await readline())) {

let tokens = line.split(" ");

input.push(line.trim());

}

const t = input[0];

for (let i = 1; i <= t; i++) {

const [n, target] = input[2 * i - 1].split(" ");

let foods = input[2 * i].split(" ");

let foodsArray = []

for(let k = 0; k < foods.length; k++) {

foodsArray.push({

value: parseInt(foods[k]),

index: k + 1

})

}

foodsArray.sort((a, b) => b.value - a.value);

let sum = 0;

let ways = "";

for (let j = 0; j < n; j++) {

sum = sum + parseInt(foodsArray[j].value);

ways = ways + ' ' + foodsArray[j].index

if (sum >= parseInt(target)) {

console.log( j + 1);

console.log(ways.trim());

sum = 0;

ways = "";

break;

}

if (j === n - 1) {

console.log(-1);

}

})();

发表于 2025-08-25 02:48:13 回复(0)

GreyPigeon

贴一份c++，常规贪心

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int nums, satiety;
        cin >> nums >> satiety;
        //> 同时记住位置
        vector<pair<int, int>> food(nums);
        for (int i = 0; i < nums; ++i)
        {
            int a;
            cin >> a;
            food[i] = {a,i+1};
        }
        sort(food.begin(), food.end(), 
             [](pair<int,int> a, pair<int,int> b)
             {return a.first > b.first;});
        int sum = 0;
        int index = 0;
        //> 贪心
        while (sum < satiety && index < nums)
        {
            sum += food[index++].first;
        }
        if (sum >= satiety)
        {
            cout << index << endl;
            for (int i = 0; i < index; ++i)
            {
                cout << food[i].second << " ";
            }
            cout << endl;
        }
        else
            cout << -1 << endl;
    }
   return 0;
}

发表于 2022-07-26 00:40:41 回复(0)