题目大意:一个n,表示有n个长条放在n行,每一个第一个数表示起点,第二个数是这个长条的长度,这个长度不包括起点,不然案例都过不了
思路:贪心
还是看图,有图还是很方便的,图给人的感觉就是先处理左区间最小的。
1.按左区间的值升序排序。
2.y记录前几个长条重合部分的末尾,如果长条i的左区间大于y,那么可以一刀切,维护y取右区间的最小值,如果大于等于y,那么就只能再多切一刀了,y取i的右区间。
3.左区间相同时,跟右区间的排序无关,左区间一样表明能一刀切下这些左区间一样的长条,假设前面的长条和后面的长条没有重合的部分,这这些左区间一样的长条不管是全站到一边,或者两边倒都是两刀,不影响结果。

Code:

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
struct node{
    int x,y;
    bool operator<(const node&a) const{
        return x<a.x;
    }
}q[50005];
int main() {
    js; int n,ans=1,tmp;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>q[i].x>>tmp,q[i].y=q[i].x+tmp;
    sort(q+1,q+1+n);
    for(int i=2,x=q[1].x,y=q[1].y,pos=1;i<=n;++i) {
        if(q[i].x>=y) {
            ++ans;
            x=q[i].x;
            y=q[i].y;
            continue;
        }
        if(q[i].x<y) y=min(y,q[i].y);
    }
    cout<<ans<<"\n";
}