AT_abc103_d 题解

Back_Stuff · 2022-11-01 19:27:52 · 题解

这题其实就是P1803 凌乱的yyy / 线段覆盖。 一道easy的与区间有关的贪心题。

思路

题目给的 n，其实根本没有用。

我们首先按照尾端点排序，首端点排不排都没关系。

定义一个 f 来记录。如果 f \leq 当前首端点，将 f 更新为当前尾端点，要拆除的桥梁数加 1。否则，f 不变。

最后输出要拆除的桥梁数即可。

代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)//优化
using namespace std;
int n,m,cnt,f=-0x3f3f3f3f,k;
struct NODE{ int s,e; }a[100001];
bool cmp(NODE a,NODE b){ return a.e<b.e; }尾端点排序
int main(){
    IOS;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i].s>>a[i].e;
    }
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(a[i].s>=f){
            f=a[i].e;
            k++;
        }
    }
    cout<<k;
    return 0;
}