切长条

典型的贪心例题

1.首先每条线段按照左端点升序排列
2.然后开始遍历，只要新的线段的左端点大于之前线段中右端点最小的端点，那么就没有重合部分，就要多砍一刀
3.否则就更新最右端的最小值，并且继续遍历

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e7 + 5;

struct node
{
    int l, r;
    bool operator<(const node x)
    {
        return l < x.l;
    }
} a[maxn];

int main()
{
    int n, len;
    while (~scanf("%d", &n))
    {
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d%d", &a[i].l, &len);
            a[i].r = a[i].l + len;
        }
        sort(a + 1, a + n + 1);
        int minn = a[1].r;
        int ans = 1; //至少砍一刀
        for (int i = 2; i <= n; ++i)
        {
            if (a[i].l >= minn)
            {
                ++ans;
                minn = a[i].r;
            }
            else
                minn = min(minn, a[i].r);
        }
        printf("%d\n", ans);
    }
}