51 Nod 1091 线段的重叠 (贪心算法)

原题链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1091

思路分析：通过读题不难发现这是一道涉及贪心算法的题，刚开始上手做也是摸不着头脑。首先把所有的线段按起点由小到大进行排序，比如（1，5），（2，4），（2，8），（3，7），（7，9），然后进行比较，每次比较保留最大的末尾数字，最终结果就是 max（min(最大末尾数字，本次末尾数字）- 本次起始数字，上次的比较结果）;

举个栗子：

/*

    1   5

    2   4

    2   8

    3   7

    7   9

*/

// 第一次

Max = 5, ans = 0;

// 第二次

Max = 5, ans = 4 - 2 = 2

// ans = max(min(5, 4) - 2, 0) = 4 

// 第三次

Max = 8, ans = 5 - 2 = 3

// Max = max(5, 8) = 8,  ans = max(min(5, 8) - 2, 2) = 3

// 第四次

Max = 8, ans = 7 - 3 = 4

// ans = max(min(8, 7) - 3, 3) = 4

// 第五次

Max = 8, ans = 4

代码如下：

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int, int> P;

const int MAX = 50000;

P a[MAX];

int n;

int main() {

	cin >> n;

	for (int i = 0; i < n; i++)

		cin >> a[i].first >> a[i].second;

	sort(a, a+n);

	int Max = a[0].second, ans = 0;

	for (int i = 1; i < n; i++) {

		ans = max(min(Max, a[i].second) - a[i].first, ans);

		Max = max(Max, a[i].second);

	}

	cout << ans << endl;

	return 0;

}

巴特西

51 Nod 1091 线段的重叠 (贪心算法)

最新文章

热门文章