专栏文章

题解：P13646 [NOISG 2016] LunchBox

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

文章操作

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

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

0：闲话

蒟蒻第一次写题解QAQ

1：做法

~明显~是一道贪心，按照需求量k[i]k[i]从小到大排序，然后再拿NN一个个减去k[i]k[i]，每减去一次，ansans就加一，直到N<k[i]N<k[i]为止，最后输出ansans即可。
为什么可以贪心？~我也不知道~ 显然，NN所能“支付”的学校数量越多越好，并且学校不管要多少饭盒，都只能对答案做出一次贡献，所以选择需求量大的学校和选择需求量小的学校结果是一样的，那么当然是选择需求量小的学校啦！

2:代码

CPP
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
	return a<b;//从小到大
}
int main(){
	int n,k,ans=0;
	int a[k+1];
	cin>>n>>k;
	for(int i=1;i<=k;i++)cin>>a[i];
	sort(a+1,a+k+1,cmp);
	for(int i=1;i<=k;i++){
		if(n<a[i])break;//坑点，千万不要 n<0 break，否则掉大分
		n-=a[i];
		ans++;
	}
	cout<<ans;
	return 0;
}

3：完结散花

评论

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

正在加载评论...