专栏文章

题解:P13646 [NOISG 2016] LunchBox

P13646题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miogmc18
此快照首次捕获于
2025/12/02 18:53
3 个月前
此快照最后确认于
2025/12/02 18:53
3 个月前
查看原文

1.题目大意

给定长度为 mm 的数组 kk,给定一个数字 NN,以及一个计数变量 cntcnt 且初始为 00,对于每一个 ki(1im)k_i(1 \le i \le m),你可以让 NN 减去 kik_i,并让 cntcnt11,你也可以不进行操作。你需要在 NN 始终大于等于 00 的情况下最大化 cntcnt 的值。

2.题目思路

考虑贪心。
要想让答案最大,我们就需要让 NN 每次减去最小的值,这样能使 NN 尽量减掉更多的 kik_i。由此想到把 kk 数组从小到大排序,这样再从头遍历一遍数组,直到 NN 不能再减,就退出循环。
时间复杂度 O(NlogN)\mathcal O(N \log N),足以通过此题。

3.代码

注:代码仅供参考。
代码CPP
#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. Luogu ryf2011\color{red}\texttt{Luogu ryf2011}
  2. cnblogs(博客园) cnblogs2011ryf\color{orange}\texttt{cnblogs(博客园) cnblogs2011ryf}

评论

0 条评论,欢迎与作者交流。

正在加载评论...