GESP2024年3月认证C++六级( 第三部分编程题（2）好斗的牛）

参考程序（暴力枚举）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> a, b;
int ans = 1e9;
int main() 
{cin >> N;a.resize(N);b.resize(N);for (int i = 0; i < N; ++i) {cin >> a[i];}for (int i = 0; i < N; ++i) {cin >> b[i];}vector<int> permutation;permutation.resize(N);for (int i = 0; i < N; i ++)permutation[i] = i;do {int curr_len = N;for (int i = 1; i < N; ++i) {curr_len += max(b[permutation[i - 1]], a[permutation[i]]);}ans = min(ans, curr_len);} while(next_permutation(permutation.begin(), permutation.end()));cout << ans << endl;return 0;
}

参考程序（贪心算法）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int N;cin >> N;vector<int> a(N), b(N);for (int i = 0; i < N; ++i) {cin >> a[i];  // 左侧攻击范围}for (int i = 0; i < N; ++i) {cin >> b[i];  // 右侧攻击范围}// 牛的放置策略：// 将每头牛的攻击范围 [a[i], b[i]] 转化为一个区间vector<pair<int, int>> cows(N);for (int i = 0; i < N; ++i) {cows[i] = {a[i], b[i]};}// 排序：根据每头牛的攻击范围进行排序sort(cows.begin(), cows.end());// 计算最少需要的牛棚数量int left = 0, right = 0;for (int i = 0; i < N; ++i) {// 当前牛的位置必须满足其攻击范围left = max(left, cows[i].first);              // 最小位置right = left + cows[i].second;                // 最大位置（放置当前牛之后的最远位置）left = right;                                 // 更新最左边界，准备放置下一个牛}cout << right << endl;  // 最终右边界即为所需的牛棚数量return 0;
}