谷歌网站站长指南/首页排名优化公司

B - 整数区间

Time Limit: 1000/1000MS (C++/Others) Memory Limit: 65536/65536KB (C++/Others)

Problem Description

一个整数区间[a,b](a < b)，是一个从a到b连续整数的集合。
现在给你n个整数区间，编程找出一个集合R，使得n个集合中的每个集合都有2个整数出现在R中，并且这个集合R包含的整数个数最少。

Input

第一行包含整数n(1 <= n <= 10000)，表示整数区间的个数。接下来n行，每行包含两个整数a和b(0 <= a < b <= 10000, a < b)。

Output

输出符合条件的集合R中元素的个数。

Sample Input

4
3 6
2 4
0 2
4 7

Sample Output

4

Hint

对于输入样例，我们可以找到集合R{1,2,4,5}和R{1,2,4,6}，这里R的元素的个数为4.

 

 

 

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;const int maxn = 1e5+5;
struct Node{int x, y;bool operator < (const Node& b) const{ // 按照b的升序排序return y < b.y;} 
}a[maxn];int main()
{int n;scanf("%d", &n);for(int i=0; i<n; i++)scanf("%d %d",  &a[i].x, &a[i].y);sort(a, a+n);int t1 = -1, t2 = -1, cnt = 0;// t1 t2表示当前取的，最大的两个数 其中 t1 < t2for(int i=0; i<n; i++){bool f1 = (t1 >= a[i].x); // t1是否在当前区间bool f2 = (t2 >= a[i].x); // t2是否在当前区间if(f1 && f2) ;  // 都在 不处理else if(!f1 && f2) { // t1不在，t2在, 需要再加一个数，替换掉t1, 贪心的取最大的t1 = a[i].y;cnt++;      // 多需要一个数
        }else {          // t1 t2谁都不在，需要再加两个数，贪心地添加最大的两个数t1 = a[i].y - 1;t2 = a[i].y;cnt += 2;}if(t1 > t2) swap(t1, t2); //保持 t1 < t2
    }printf("%d\n", cnt);return 0;
}