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 
#include 
using namespace std;

typedef pair 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 线段的重叠 (贪心算法)

相关

标签