专栏文章
题解:P13646 [NOISG 2016] LunchBox
P13646题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miogmc18
- 此快照首次捕获于
- 2025/12/02 18:53 3 个月前
- 此快照最后确认于
- 2025/12/02 18:53 3 个月前
1.题目大意
给定长度为 的数组 ,给定一个数字 ,以及一个计数变量 且初始为 ,对于每一个 ,你可以让 减去 ,并让 加 ,你也可以不进行操作。你需要在 始终大于等于 的情况下最大化 的值。
2.题目思路
考虑贪心。
要想让答案最大,我们就需要让 每次减去最小的值,这样能使 尽量减掉更多的 。由此想到把 数组从小到大排序,这样再从头遍历一遍数组,直到 不能再减,就退出循环。
时间复杂度 ,足以通过此题。
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.后记
更多内容,请移步至:
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...