用C++实现假设你是黄牛,用贪心算法找到月饼的最佳买卖时机,输出最大获益。 输入 [7,1,5,3,6,4] 输出 5
时间: 2024-06-14 14:06:08 浏览: 122
以下是用C++实现贪心算法找到月饼的最佳买卖时机,输出最大获益的代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int maxProfit(vector<int>& prices) {
int maxProfit = 0;
int minPrice = INT_MAX;
for (int i = 0; i < prices.size(); i++) {
if (prices[i] < minPrice) {
minPrice = prices[i]; } else if (prices[i] - minPrice > maxProfit) {
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}
int main() {
vector<int> prices = {7, 1, 5, 3, 6, 4};
int maxProfit = maxProfit(prices);
cout << "最大获益为:" << maxProfit << endl;
return 0;
}
```
相关问题
C++用贪心算法输出最大数
可以使用贪心算法来输出一个数字的最大排列。一种常见的方法是将数字转换为字符串,然后对字符串进行排序。排序时,我们可以定义一个比较函数,使得两个字符串拼接起来的结果更大的字符串排在前面。下面是一个示例代码:
```c++
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool compare(string a, string b) {
return a + b > b + a;
}
int main() {
int n;
cin >> n;
string nums[n];
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
sort(nums, nums + n, compare);
for (int i = 0; i < n; i++) {
cout << nums[i];
}
cout << endl;
return 0;
}
```
这里我们定义了一个比较函数 `compare`,它返回两个字符串拼接起来的结果更大的字符串排在前面。然后我们读入数字,将它们转化为字符串,并按照 `compare` 函数进行排序。最后输出排列好的字符串即可。
活动安排问题,使用贪心算法用c++实现
假设你有一些活动需要安排,每个活动都有一个开始时间和结束时间。你需要从这些活动中选择一些活动来安排,使得每个时间段内都只有一个活动在进行。请问,你最多可以安排多少个活动?
这是一个经典的贪心算法问题,我们可以按照结束时间从小到大排序,然后依次选择结束时间最早的活动,直到所有活动都被安排。
下面是使用 C++ 实现的贪心算法代码:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activity {
int start, end;
};
bool cmp(Activity a, Activity b) {
return a.end < b.end;
}
int maxActivities(vector<Activity>& activities) {
// 按结束时间从小到大排序
sort(activities.begin(), activities.end(), cmp);
int count = 1;
int end = activities[0].end;
for (int i = 1; i < activities.size(); i++) {
// 如果下一个活动的开始时间大于等于上一个活动的结束时间,就可以安排这个活动
if (activities[i].start >= end) {
count++;
end = activities[i].end;
}
}
return count;
}
int main() {
vector<Activity> activities = {{1, 3}, {2, 5}, {3, 7}, {4, 8}, {5, 9}, {6, 10}, {8, 11}};
cout << maxActivities(activities) << endl; // 输出 4
return 0;
}
```
上面的代码中,我们定义了一个结构体 `Activity` 来表示活动的开始时间和结束时间。然后我们定义了一个自定义比较函数 `cmp`,用来按照结束时间从小到大排序。接着我们定义了一个函数 `maxActivities` 来计算最多可以安排多少个活动。
在 `maxActivities` 函数中,我们首先对活动按照结束时间从小到大排序。然后从第一个活动开始,依次判断下一个活动的开始时间是否大于等于上一个活动的结束时间,如果是,就可以安排这个活动,并更新当前的结束时间 `end`。最后返回安排的活动数量即可。
最后在 `main` 函数中,我们定义了一些活动,然后调用 `maxActivities` 函数来计算最多可以安排多少个活动,输出结果为 4。