#创作计划#小学牲和贪心
2025-07-26 17:19:10
发布于：浙江
4阅读
0回复
0点赞
进来的打个1呗
贪心算法，真的不用我讲了
题目放在最后
贪心的例子1：
加勒比海盗最优装载问题（简单版）
（相信大家都知道，就不多说了(bushi)）
简单策略就是sort，之后再从大到小装载，代码：
#include<bits/stdc++.h>
using namespace std;
int n,r,arr[10001],tem=0,cnt=0;
bool cmp(int x,int y) {
return x>y;
}
int main() {
cin>>n>>r;
for(int i=1;i<=n;i++) {
cin>>arr[i];
}
sort(arr,arr+n+1,cmp);
for(int i=1;i<=n;i++) {
tem+=arr[i];
if(r>tem) {
break;
} else {
cnt++;
}
}
cout<<cnt<<" "<<tem;
return 0;
}
真的，不难！！！
贪心的例子2：
加勒比海盗最优装载问题（一般版）
这道题其实就是部分背包问题，先计算出每一滩金砂的价值（因为已经保证了是整数），简单加个判断就好了。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,r,arr[10001],t,jia,tem=0,cnt=0;
bool cmp(int x,int y) {
return x>y;
}
int main() {
cin>>n>>r;
for(int i=1;i<=n;i++) {
cin>>ti>>jia;
arr[i]=ti/jia;
}
sort(arr,arr+n+1,cmp);
for(int i=1;i<=n;i++) {
tem+=arr[i];
if(r>tem) {
break;
} else {
cnt++;
}
}
cout<<cnt<<" "<<tem;
return 0;
}
贪心的例子3：
跑步机问题
这个问题也不是不可以用贪心做，但是可能会翻车（真的，我亲测），所以一定要DP！！！
大体的贪心结构也是恢常简单，就不放代码了，免得大家WA（这道题我即将再团队里出）
题目详解：
题目1：
有一群加勒比海盗，入侵了非洲（bushi），他们在非洲找到了n件宝物，但是串只能装载w千克的宝物，输入n，再输入这些宝物的重量，输出最多可以拿几件宝物。
题目2：
这群加勒比海盗又入侵了非洲，他们在非洲发现了n堆金沙，每堆金沙都有质量s和纯度e，总之价值是s/e，保证为整数，现在，大家只能抢n的总价值，输入n,arr,n个s,n个e，输出堆数和总价值之和（这道题似乎和正版有点不一样？）
题目3：
小王同学爱跑步机，现在有两台跑步机，第一台跑步机需要a分钟锻炼出一块肌肉，第二个跑步机需要b分钟锻炼出一块肌肉，每锻炼出一块肌肉，那个跑步机的时间（a或b）+1，请问小王最少需要多少时间才能锻炼出10000块肌肉 ？输入a和b，输出时间。（注意，本题容易TLE，请优化算法）
这里空空如也
有帮助，赞一个