首页 > 代码库 > 51node1091(贪心)

51node1091(贪心)

2024-08-31 13:58:26   219人阅读

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

 

题意：中文题诶～

 

思路：贪心；

我们先将数据按照左端点升序排列，对于左端点一样的区间我们再按照右端点升序排列；其实对于左端点相同的区间影响答案的只是其中右端点最大的那个区间，我们可以将右端点坐标较小的区间去掉，不过那样操作比较麻烦，就不必去掉他们啦．这点很简单，就不细说了；

假设我们将排序后的数据存储到gg结构体数组中，我们先令end=gg[0].right, ans=0，ans存储但前最大公共区间值；那么在gg[0]后面的区间与gg[0]有三种关系：

１：gg[i].left>end, 即gg[i]与gg[0]不相交．此时我们要更新end＝gg[i].end，因为我们是按照left升序怕排列gg的，所以在当前情况下gg[0]后面的区间都不会与gg[0]相交啦；

２：gg[i].left<end，此种情况根据gg[i].right的大小又可以细分两种情况：

　　a: gg[i].right<end, 此时我们需要检查是否要更新ans, ans=max(ans, end-gg[i].left)；

　　B: gg[i].right>＝end，此时我们不仅要更新ans, 还要更新end, end=gg[i].right；

如此遍历完gg数组，ans就是我们要的答案啦；

 

代码：

 1 #include <bits/stdc++.h>
 2 #define MAXN 50010
 3 using namespace std;
 4 
 5 struct node{
 6     int left, right;
 7 };
 8 
 9 bool cmp(node a, node b){
10     return a.left==b.left?a.right<b.right:a.left<b.left;
11 }
12 
13 int main(void){
14     int n;
15     node gg[MAXN];
16     cin >> n;
17     for(int i=0; i<n; i++){
18         cin >> gg[i].left >> gg[i].right;
19     }
20     sort(gg, gg+n, cmp);
21     int ans=0, end=gg[0].right;
22     for(int i=1; i<n; i++){
23         if(gg[i].left<end){
24             if(gg[i].right<end){
25                 ans=max(ans, gg[i].right-gg[i].left);
26             }else{
27                 ans=max(ans, end-gg[i].left);
28                 end=gg[i].right;
29             }
30         }else{
31             end=gg[i].right;
32         }
33     }
34     cout << ans << endl;
35     return 0;
36 }

 

51node1091(贪心)


联系
我们