题解：P13646 [NOISG 2016] LunchBox

ryf2011 · 2025-08-08 12:00:33 · 题解

1.题目大意

给定长度为 m 的数组 k，给定一个数字 N，以及一个计数变量 cnt 且初始为 0，对于每一个 k_i(1 \le i \le m)，你可以让 N 减去 k_i，并让 cnt 加 1，你也可以不进行操作。你需要在 N 始终大于等于 0 的情况下最大化 cnt 的值。

2.题目思路

考虑贪心。

要想让答案最大，我们就需要让 N 每次减去最小的值，这样能使 N 尽量减掉更多的 k_i。由此想到把 k 数组从小到大排序，这样再从头遍历一遍数组，直到 N 不能再减，就退出循环。

时间复杂度 \mathcal O(N \log N)，足以通过此题。

3.代码

注：代码仅供参考。

:::info[代码]{open}

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int max_m=60002;
int n,m,k[max_m],l,ans;
long long sum;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&k[i]);
    }
    sort(k+1,k+m+1); //排序
    l=1; //初始化
    while(sum+k[l]<=n&&l<=m){
        sum+=k[l]; //求和
        ans++; //计数+1
        l++; //指针+1
    }
    printf("%d\n",ans);
    return 0;
}

:::

4.后记

更多内容，请移步至：

1. \color{red}\texttt{Luogu ryf2011}；
2. \color{orange}\texttt{cnblogs（博客园） cnblogs2011ryf}。