切长条

题目描述

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

注意：输入文件每行的第一个数表示开始的位置，而第二个数表示长度。

思路

用贪心的思路解题，首先我们应该把数据转化为[起始点，结束点]这种形式，然后我们可以对起始点进行结构体排序，这样从1~n起始点是依次增大的，for循环遍历结构体数组，同时更新一个结束点的最小值。当遍历到i点时，结束点最小值<=此时的起始点，竖线条数加一。
我们看一下样例排序后的样子（让我搞不懂的是起始点竟然不算在长度里面。。。。）：

判断点在第六行，起始点是7，而结束点最小值值是6，竖线加一。

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
pair<ll,ll>a[40000];//相当于有两个变量的结构体。
int main()
{
    int n;cin>>n;
    for (int i = 0; i < n; i++)
        cin>>a[i].first>>a[i].second,a[i].second+=a[i].first;
    sort(a,a+n);//pair默认对第一个数据进行排序
    ll minn=a[0].second;
    int ans=0;//竖线条数
    for (int i = 1; i < n; i++)
    {
        minn=min(minn,a[i].second);
        if(minn<=a[i].first) ans++,minn=a[i].second;//判断并更新结束点最小值
    }
    cout<<ans+1<<endl;
    return 0;
}