题目大意:一个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";
} 
京公网安备 11010502036488号