切长条

切长条

题目描述

给定如图所示的若干个长条。你可以在某一行的任意两个数之间作一条竖线，从而把这个长条切开，并可能切开其他长条。问至少要切几刀才能把每一根长条都切开。样例如图需要切两刀。 注意：输入文件每行的第一个数表示开始的位置，而第二个数表示长度。

输入描述:

Line 1: A single integer, N(2 <= N <= 32000)Lines 2..N+1: Each line contains two space-separated positive integers that describe a leash. The first is the location of the leash's stake; the second is the length of the leash.(1 <= length <= 1e7)

输出描述:

Line 1: A single integer that is the minimum number of cuts so that each leash is cut at least once.
​

输入

7
2 4
4 7
3 3
5 3
9 4
1 5
7 3

输出

2

题目大意

若干长条，最少多少刀，全部切开

思路

按左端点排序 不断更新最小右端点，如果左端点大于等于最小右端点，则不重合，需要切一刀，最后要加上一刀

#include<bits/stdc++.h>
using namespace std;
struct date{
 int l=0;
 int r=0;
}F[32005];
bool cmp(date a,date b){
 return a.l<b.l;
}
int main()
{
 //任意两个数之间做竖线，切开长条，至少几刀都切开
 //当起点，大于等于排序后前一个点的时候(最小值)，给一刀 
 int n,sum=0;
 scanf("%d",&n);
 for(int i=0;i<n;i++)
 {
  scanf("%d%d",&F[i].l,&F[i].r);
  F[i].r=F[i].l+F[i].r;
 }
 sort(F,F+n,cmp);
 int minn=F[0].r;
 for(int i=1;i<n;i++)
 {
  minn=min(minn,F[i].r);
  //更新最新最小右端点 
  //printf("前r和现r的最小值=%d ",minn); 
        if(F[i].l>=minn) sum++,minn=F[i].r;//判断并更新结束点最小值
  //printf("l=%d r=%d min2=%d\n",F[i].l,F[i].r,minn);
  }
 printf("%d",sum+1);
 return 0;
 }