复兴无基础第二十课 贪心
2025-10-18 20:25:47
发布于：上海
4阅读
0回复
0点赞
T1【贪心算法(一)】书架
#include <iostream>
#include <algorithm>
using namespace std;
int a[20010];
//定义排序规则，将数从大到小排序
bool cmp(int x, int y){
return x>y;
}
int main() {
//定义奶牛数量n和书架高度b，并且输入
int n, b;
cin >> n >> b;
//输入n个奶牛的身高
for(int i = 1; i <= n; i++){
cin >> a[i];
}
//从大到小排序n个奶牛的身高
sort(a + 1,a + n + 1,cmp);
//定义两个变量，分别为当前已选的奶牛高度和数量
int sum = 0, cnt = 0;
for(int i = 1; i <= n; i++){
//当前加上选择的奶牛高度使得总高度增加，数量+1
sum += a[i];
cnt++;
//当前加上选择的奶牛高度大于书架的高度，那么退出
if(sum >= b){
break;
}
}
//输出选择的奶牛数量
cout << cnt;
return 0;
}
T2【贪心算法(一)】三角形的最大周长
#include<iostream>
#include<algorithm>
using namespace std;
int arr[110];
//定义排序规则进行降序排序
bool cmp(int x,int y){
return x>y;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
//将当前的数组从大到小进行排序
sort(arr+1,arr+1+n,cmp);
//定义一个标记标记我们并未找到
bool flag=false;
//for循环的方式从前往后找到满足条件的三角形边长
for(int i=1;i<=n-2;i++){
//当我们短的两个边相加大于第三边，输出周长，标记已找到
if(arr[i+1]+arr[i+2]>arr[i]){
flag=true;
cout<<arr[i]+arr[i+1]+arr[i+2]<<endl;
break;
}
}
//直到最后依旧没有找到符合条件的边
if(flag==false)cout<<0<<endl;
return 0;
}
T3【贪心算法(一)】打折糖果
#include<iostream>
#include<algorithm>
using namespace std;
int arr[110];
//定义排序规则进行降序排序
bool cmp(int x,int y){
return x>y;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
//将当前的数组从大到小进行排序
sort(arr+1,arr+1+n,cmp);
//定义变量表示买完糖果的花费
int sum=0;
//从价格高的糖果开始购买
for(int i=1;i<=n;i+=3){
sum+=arr[i];
if(i+1<=n)sum+=arr[i+1];
}
//最后输出小码君的花费
cout<<sum<<endl;
return 0;
}
T4【贪心算法(一)】接水问题
#include <iostream>
#include <algorithm>
using namespace std;
//定义数组储存当前的人的接水耗时
int a[1020];
int main() {
//输入n和n个接水的人的用时
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin>>a[i];
}
//将n个人的接水用时从小到大排序
sort(a+1,a+n+1);
//定义一个double变量用于储存所有人的接水等待时间
double sum = 0;
//用for循环将当前人接水等待的时间加到总和中
for(int i = 1; i <= n; i++){
sum += a[i] * (n - i);
}
//输出平均值
printf("%.2f", sum / n);
return 0;
}
T5【贪心算法(一)】最优装载问题
#include <iostream>
#include <algorithm>
using namespace std;
int w[1010];
int main() {
int c, n;
//输入载重量和古董的件数
cin >> c >> n;
//输入n件古董
for(int i = 0; i < n; i++){
cin >> w[i];
}
//对数组进行升序排序
sort(w,w + n);
//已装载的古董的总质量
double tmp = 0.0;
//已装载的古董的总数量
int ans = 0;
for (int i = 0; i < n; i++){
tmp += w[i];
//通过循环判断是否已经达到载重量
if (tmp <= c){
ans++;
}
else{
break;
}
}
//输出最多装载古董数量
cout << ans;
return 0;
}
T6【贪心算法(一)】粮草
#include <iostream>
#include <algorithm>
using namespace std;
//定义结构体储存粮草的价格和数量
struct node{
int p;
int a;
}b[5010];
//定义结构体排序，将单价低的粮草排在前面
bool cmp(node x, node y){
return x.p<y.p;
}
int main() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> b[i].p >> b[i].a;
}
//将粮草的花费从小到大排序
sort(b + 1, b + m + 1, cmp);
int sum = 0;
for(int i = 1; i <= m; i++){
//如果当前需求粮草小于等于农户粮草
if(n - b[i].a <= 0){
sum += n * b[i].p;
break;
}
//如果当前需求粮草大于农户粮草
n -= b[i].a;
sum += b[i].a * b[i].p;
}
//输出购买粮草的花费
cout << sum;
return 0;
}
T7【贪心算法(一)】接水问题二
#include <iostream>
#include <algorithm>
using namespace std;
//定义结构体储存当前的人的接水耗时和下标
struct node{
int t;
int id;
}a[1010];
//定义排序规则让接水时间短的人先去接水
bool cmp(node x, node y){
return x.t<y.t;
}
int main() {
int n;
//输入n和n个接水的人的用时
cin >> n;
for(int i = 1; i <= n; i++){
cin>>a[i].t;
//当前接水的人的id赋值
a[i].id = i;
}
//将n个人的接水用时从小到大排序
sort(a + 1, a + n + 1, cmp);
//定义一个double变量用于储存所有人的接水等待时间
double sum = 0;
//用for循环将输出接水的人的编号以及将当前人接水等待的时间加到总和中
for(int i = 1; i <= n; i++){
cout << a[i].id << " ";
sum += a[i].t * (n - i);
}
cout<<endl;
//输出平均值
printf("%.2f", sum / n);
return 0;
}
T8【贪心算法(一)】骑士的工作
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e4 + 10;
// 龙的头的大小
int head[20010];
// 骑士的能力(砍掉的头的大小)
int gold[20010];
int main() {
int n, m;
// 输入n和m以及龙的n个头和m个骑士
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> head[i];
}
for(int i = 1; i <= m; i++) {
cin >> gold[i];
}
//将龙头和骑士从小到大排序
sort(head + 1, head + n + 1);
sort(gold + 1, gold + m + 1);
//龙和骑士初始都从1开始选取
int i = 1, j = 1;
//定义最小花费和砍下来头的数量
int sum = 0;
int cnt = 0;
//通过while循环的方式砍龙头
while(i <= n && j <= m) {
// 第 i 个头能够被第 j 个骑士砍掉
if(head[i] <= gold[j]) {
//花费增加，砍下的头数加 1，将龙的下标和骑士的下标往后移动一位
sum += gold[j];
cnt++;
i++;
j++;
}
else {//如果砍不掉换下一个骑士继续尝试
j++;
}
}
//如果砍完了，输出最小花费
if(cnt == n) cout << sum;
else cout << "you died!";
return 0;
}
这里空空如也
有帮助，赞一个