P2207 Photo B 题解

· · 题解

每两只奶牛的关系可以视为一个区间，等于说我们需要尽可能少地在[1,n]上的整点取点，确保每个区间里都有一个点

而众所周知，存在许多相交的区间，如果我们尽可能把点放在交集中的话，那就好了

而后我就想出了一个方法

我们持续性地对较为靠近的两个区间作交集运算，直到眼下这个集不再和任何一个附近的区间成交集，那么只要在这个小的交集中放一个点，就能确保这个交集的所有母集中都能至少有一个点

相当于是每次两两合并一个区间

为了确保运算效率最高，我们考虑贪心，把区间从小到大排一遍，按照左端点或右端点排序都无所谓

每次只要眼下的交集不能和任何一个剩余的区间作交集时，就让答案加一

最后再将答案加一即可

需要注意的是输入数据不确保a<b所以必须输入时就比较预处理

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
int n,k; 
struct line{
    int l,r;
}sorted[1005];
bool cmp(line a, line b){
    if(a.r > b.r)return true;
    return false;
}
stack<line> cows;
int main(){
    cin >> n >> k;
    for(int i=0;i<k;i++){
        int left,right;
        cin >> left >> right;
        sorted[i].l = min(left,right);
        sorted[i].r = max(left,right);
    }
    sort(sorted,sorted+k,cmp);
    for(int i=0;i<k;i++)cows.push(sorted[i]);
    int ans = 0;
    while(!cows.empty()){
        line top1 = cows.top();
        cows.pop();
        if(cows.empty()){
            ans++;
            break;
        }
        line top2 = cows.top();
        cows.pop();
        if(top1.r > top2.l){
            line tmp;
            tmp.l = top2.l;
            tmp.r = top1.r;
            cows.push(tmp);
        }
        else{
            ans++;
            cows.push(top2);
        }
    }
    cout << ans+1 << endl;
    return 0;
}