B - 整数区间 - 开发语言

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

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=; i<n; i++)

        scanf("%d %d",  &a[i].x, &a[i].y);

    sort(a, a+n);

    int t1 = -, t2 = -, cnt = ;

    // t1 t2表示当前取的，最大的两个数 其中 t1 < t2

    for(int i=; 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 - ;

            t2 = a[i].y;

            cnt += ;

        }

        if(t1 > t2) swap(t1, t2); //保持 t1 < t2

    }

    printf("%d\n", cnt);

    return ;

}