题目大意:一个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"; }