#include<bits/stdc++.h> using namespace std; int main(){ int c,n,a[1111],b=0; cin>>c>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+n+1); for(int i=1;i<=n;i++){ if(c>=a[i]){ c-=a[i]; b++; }else{ break; } } cout<<b; return 0; }

题解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这是一道贪心模版题。 大概意思就是，需要尽可能多的数量，来装一定量的货物。这就是贪心算法的思想：一步最优达到全局最优。 首先，我们需要对其重排序，才能找到质量最轻的货物。 然后，循环枚举该数组，如果货物没超限就加上，否则终止循环。 这里提供复杂度为 O(n)O(n)O(n) 的答案。

#include<bits/stdc++.h> using namespace std; int main(){ int c,n; cin>>c>>n; int w[1010]; for(int i=1;i<=n;i++){ cin>>w[i]; } sort(w+1,w+n+1); int cnt=0; for(int i=1;i<=n;i++){ if(c-w[i]>=0){ cnt+=1; c-=w[i]; } } cout<<cnt; }

优先队列不进行完整排序，而且内存占用随测试点大小变化，理论上更好 代码：

废话少说，上代码

题意 海盗船有最大载重量 k，一共有 n 件古董，每件古董重量不同。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 思路 要装数量最多，就必须优先装最轻的古董，这是典型的贪心策略： 1.输入载重量 k、古董数量 n，以及所有古董重量； 2.将所有古董按重量从小到大排序； 3.从最轻的开始一件件装船，能装就装，装不下就停止； 4.统计一共装了多少件，输出答案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 完整代码

题目大意 在载重量 CCC 之内求得最多能获取的古董数量 考纲知识点 输入输出、分支结构、循环结构、一维数组、算术运算符、sortsortsort 排序、自定义函数、贪心算法、基础数据类型、变量的定义以及使用 解题思路 要想获取更多的古董，就需要保持古董的重量不超过载重量 CCC ，所以古董的重量越小越好 用 sortsortsort 排序从小到大升序排序，排序后就是古董重量小的排在前面 定义一个 cntcntcnt 变量记录目前可以装的古董数量，sumsumsum 记录当前的重量 如果古董目前的重量和要加的古董重量超出了海盗船的载重量 CCC ，就结束循环 没有超过载重量 CCC 就让 sumsumsum 加上这个古董的重量，cntcntcnt 自增 参考程序 时间复杂度 O(nO(nO(n log n)n)n)(线性对数时间复杂度) 空间复杂度 O(n)O(n)O(n)(线性空间复杂度)

题解（解释在文中的注释）——————————————————————————————————————————————————————————————————————————

先看代码 代码是自己写的，注释是自己加的 代码是自己写的，注释是自己加的 代码是自己写的，注释是自己加的 直接抄上去可以AC~

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 不废话，先上代码：（贪心代码，时间复杂度O(N)） 思路分析（重点！！！） 1，输入C，N，数组（废话） 2，排序（贪心必备） 3，循环计数（计算装的宝物）（从小到大，应为多装小的可以装更多） 4，输出（……） 注意(!!!)： 如果因为船装不下了而结束程序，输出要减一，因为船已经超载了！！！ @Blake的主页 我的精选题单(精选?)

观察题目发现物品不能分割，只有选与不选两种选择，为了数量最大，就尽可能的先装小的，所以用sort排序 时间复杂度:O(n) 代码

#include<bits/stdc++.h> using namespace std; int main(){ int c,n,a[1111],b=0; cin>>c>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+n+1); for(int i=1;i<=n;i++){ if(c>=a[i]){ c-=a[i]; b++; }else{ break; } } cout<<b; return 0; }

#include<bits/stdc++.h> using namespace std; long long n[10000010]; int main(){ int a,b; cin>>b>>a; for(int i = 1;i<=a;i++){ cin>>n[i]; } sort(n+1,n+a+1); int o = 0,p = 0; for(int i = 1;i<=a;i++){ if(o+n[i]<=b){ o+=n[i]; p++; }else{ break; } } cout<<p; }