首页 > 代码库 > 【WikiOi 1214】线段覆盖

【WikiOi 1214】线段覆盖

2024-07-09 06:14:20   262人阅读

题目描述 Description

    给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些坐标都是区间 （－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共 点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。

输入描述 Input Description

    输入第一行是一个整数N。接下来有N行，每行有二个空格隔开的整数，表示一条线段的二个端点的坐标。

输出描述 Output Description

    输出第一行是一个整数表示最多剩下的线段数。

样例输入 Sample Input

3

6  3

1  3

2  5

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

0<N<100

分析：
算导上的例题……贪心正确性的证明详见算导→_→ 
另外这里应用了基于位异或运算的swap操作,省略了临时变量。

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 struct line
 5 {
 6     int L, R;
 7     line(){;}
 8 }Line[102];
 9 bool operator<(line a, line b)
10 {
11     return (a.R < b.R);
12 }
13 int N, ans = 1;
14 int main()
15 {
16     int i;
17     ios::sync_with_stdio(0);
18     cin >> N;
19     for(i = 0; i < N; ++i)
20     {
21         int &l = Line[i].L, &r = Line[i].R;
22         cin >> l >> r;
23         if(l > r)
24             l ^= r ^= l ^= r;
25     }
26     sort(Line, Line+N);
27     int last = Line->R;
28     for(i = 1;i < N; ++i)
29         if(Line[i].L >= last)
30         {
31             ++ans;
32             last = Line[i].R;
33         }
34     cout << ans;
35     return 0;
36 }


联系
我们