复兴无基础第二十一课 贪心（二）
2025-10-19 19:22:52
发布于：上海
0阅读
0回复
0点赞
T1【贪心算法(二)】分发饼干
#include <algorithm>
#include <iostream>
using namespace std;
//g为饼干的大小，c孩子所需的饼干大小
int g[10010], c[10010];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> g[i];
}
for (int i = 0; i < m; i++) {
cin >> c[i];
}
//将饼干大小和孩子所需的饼干大小从小到大排序
sort(g, g + n);
sort(c, c + m);
// 记录当前有多少个孩子满足
int ans = 0;
// 分别表示饼干和孩子的下标
int i = 0, j = 0;
while (i < n && j < m) {
// 当前的饼干大小可以满足下标为j的孩子
if (g[i] >= c[j]) {
// 将人和饼干往后移动一位，满足的人数+1
i++;
j++;
ans++;
} else {
i++;
}
}
// 输出满足的人数
cout << ans << endl;
return 0;
}
T2【贪心算法(二)】游玩
#include <algorithm>
#include <iostream>
using namespace std;
int arr[1010];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 按照体重从轻到重排序
sort(arr, arr + n);
// 建立双指针，一个指针从头选择重量小的人，另一个从尾选择重量大的人
int i = 0;
int j = n - 1;
// 统计需要多少条船
int ans = 0;
while (i <= j) {
// 当前体重最轻的人和体重最重的人并未超出船的上限
if (arr[i] + arr[j] <= m) {
i++;
j--;
}
// 超出船的上限，体重重的人一个人坐船
else {
j--;
}
// 船的数量+1
ans++;
}
cout << ans << endl;
return 0;
}
T3【贪心算法(二)】活动安排
#include <algorithm>
#include <iostream>
using namespace std;
// 定义结构体，参数为开始时间和结束时间
struct node {
int s, e;
} a[1010];
// 排序，将结束时间早的排序在前面
bool cmp(node a, node b) {
return a.e < b.e;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].s >> a[i].e;
}
sort(a, a + n, cmp);
// 定义变量为活动结束时间，以第一个数结尾作为活动结束时间
int last = a[0].e;
// 活动的参加数量
int num = 1;
for (int i = 1; i < n; i++) {
// 当前活动的开始时间是大于等于活动结束时间
if (a[i].s >= last) {
// 活动选取数量+1,更新活动结束时间
num++;
last = a[i].e;
}
}
// 输出活动的参加数量
cout << num;
return 0;
}
T4【贪心算法(二)】柠檬水找零
#include <algorithm>
#include <iostream>
using namespace std;
int arr[1004];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
// 两个变量表示当前手中拥有的5元和10元钞票的张数
int five = 0, ten = 0;
// 设定变量假设当前可以成功
bool flag = true;
for (int i = 1; i <= n; i++) {
// 如果当前是5元那么直接手下，5元钞票数量+1
if (arr[i] == 5) {
five++;
}
// 如果当前是10元的话，那么判断自己5元的数量是否足够
else if (arr[i] == 10) {
// 不成功找零更改标记，退出循环，可以找零5元钞票-1，10元钞票+1
if (five == 0) {
flag = false;
break;
} else {
five--;
ten++;
}
}
// 如果当前是20元的话，那么判断是否可以找零
else {
// 首先判断是否存在一张10元、一张5元，不存在再判断是否存在3张5元，都不存在修改标记退出循环
if (five > 0 && ten > 0) {
five--;
ten--;
} else if (five >= 3) {
five -= 3;
} else {
flag = false;
break;
}
}
}
// 判断标记是否为可以找零，输出对应的true和false
if (flag == true) {
cout << "true" << endl;
}
else {
cout << "false" << endl;
}
}
T5【贪心算法(二)】纪念品分组
#include <iostream>
#include <algorithm>
using namespace std;
int w, n, ans;
int p[30010];
int main() {
cin >> w >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i];
}
//对物品从小到达排序
sort(p + 1, p + n + 1);
//左右指针，指向首尾元素
int l = 1, r = n;
while (l <= r) {
//如果当前最重的和最轻的可以放下那么物品i和物品j分一组
if (p[l] + p[r] <= w) {
l++;
r--;
ans++;
}
//否则物品j单独一组
else {
r--;
ans++;
}
}
//输出分组的组数
cout << ans;
return 0;
}
T6【贪心算法(二)】跳跃游戏
#include <iostream>
using namespace std;
int arr[1002];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 定义标记标记最远跳跃距离
int ans = 0;
// 定义标记标记当前是否可以跳跃到最后一个位置
bool flag = false;
for (int i = 0; i < n; ++i) {
// 如果当前位置小于最远跳跃距离
if (i <= ans) {
// 当前位置可以跳跃出的最大距离是否比记录的距离远
ans = max(ans, i + arr[i]);
// 如果当前记录的距离大于最后一个点，那么就可以跳跃
if (ans >= n - 1) {
flag = true;
break;
}
}
}
// 能够到达最后一个下标，返回true，否则，返回false。
if (flag == true)
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}
T7【贪心算法(二)】老鼠吃奶酪
#include <algorithm>
#include <iostream>
using namespace std;
int a[1002], b[1002], c[1002];
bool cmp(int x, int y) {
return x > y;
}
int main() {
int n, k;
cin >> n >> k;
// 统计假设全部给鼠2
int sum = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
sum += b[i];
}
// 求出每一块奶酪分给a老鼠和b老鼠的差值
for (int i = 0; i < n; i++) {
c[i] = a[i] - b[i];
}
// 从大到小排序排序，如何取差距最大的k个，给老鼠a
sort(c, c + n, cmp);
for (int i = 0; i < k; i++) {
sum += c[i];
}
cout << sum << endl;
return 0;
}
这里空空如也
有帮助，赞一个