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;
}