[AtCoderABC103D] Islands War (贪心，思维)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：https://abc103.contest.atcoder.jp/tasks/abc103_d

有n个岛练成一条线，每两个岛之间有一个桥。现在有m个岛之间发生了冲突，发生冲突的岛就不能连通了，问最少要切断几座桥？

这题很有意思，贪心地去考虑，希望切到的边影响尽可能地大，可以考虑贪心地将发生冲突的右端点从小到大排，然后从左到右开始切。

可以反证一下：假如选中的某次冲突的右端点不是最优的解，那么可能存在一个在此点左侧的点待切，显然存在的左侧点不是最优点，因为左侧已经统计完将此点之前发生冲突的点对分割开的桥数，再添加一条是冗余的。

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
31
32
33
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
using pii = pair<int, int>;
const int maxn = 100100;
int n, m;
pii p[maxn];

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&n,&m)) {
    for(int i = 1; i <= m; i++) {
      scanf("%d%d",&p[i].first,&p[i].second);
      if(p[i].first > p[i].second) swap(p[i].first, p[i].second);
    }
    sort(p+1, p+m+1, [](pii x, pii y){
      if(x.second != y.second) return x.second < y.second;
      return x.first < y.first;
    });
    int tot = 1;
    int pre = p[1].second;
    for(int i = 2; i <= m; i++) {
      if(pre > p[i].first) continue;
      else {
        tot++;
        pre = p[i].second;
      }
    }
    printf("%d\n", tot);
  }
  return 0;
}