UVa 13079 - On the beach

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在炎炎夏日的海邊,需要建立地下通道,把所有海岸飯店聯通在一起,請問最少地下通道個數為何?

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
4
1 4
6 15
2 10
12 20
2
1 4
4 8
2
1 4
3 8
0

Sample Output

1
2
3
2
2
1

Solution

把這些區間排序,根據左端點由小到大開始貪心,可行解若看成一個區間,隨著區間加入,右端點會逐漸地靠近左端點,若產生無解,勢必要建立一個新通道。不斷地貪心,最後可得到最少通道個數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

int main() {
int N;
while (scanf("%d", &N) == 1 && N) {
vector<pair<int, int>> A;
int L, R;
for (int i = 0; i < N; i++) {
scanf("%d %d", &L, &R);
A.push_back(make_pair(L, R));
}
sort(A.begin(), A.end());

int ret = 0;
int PQ = INT_MAX;
for (int i = 0; i < N; i++) {
int line_x = A[i].first;
if (PQ != INT_MAX && PQ <= line_x) {
ret++;
PQ = INT_MAX;
}
PQ = min(PQ, A[i].second);
}
if (PQ != INT_MAX)
ret++;
printf("%d\n", ret);
}
return 0;
}