一开始看到英文题就没太想写。。

题目

题目概要（魔改）：
有好多个直的长条，一盘排排放好，给你长条的首尾坐标。
一道可以切开两个坐标之间的位置，用最少的刀数切开所有的长条。

输入描述：
第一行是长条数N(2 <= N <= 32000)。
第二行到n + 1行输入每一个长条的首坐标以及长条的长度。

输出描述：
一行表示最少用的长条数。

解析

这道题当然也就是个简单的贪心。
  • 而且这道题也是我们熟悉的类型：求一个区间内最短的不相交区间的最大区间数。


贪心策略：
  1. 为啥说这个切长条也是这种类型呢？因为只要区间有重复，表示这个区间一定可以在切其他区间的同时把这个区间切开！
  2. 所以就变成了求最大的不相交区间数量。那这个怎么求呢？
  3. 就是按照结束时间来排序。
  4. 为啥按照结束时间来排呢？因为上一个越早结束，下一个开始的时间就越早，选择的空间就越大。
  5. 如果有重复的也没有关系哦，比如1-3和2~3，选啥都无所谓，反正我选了，你就不能选呗。


然后操作了：
  1. 这个题目可以直接定义一个结构体，然后结构体内置排序。
  2. 这里我为了熟悉用pair，所以给pair写了一个排序函数，问题不大。


打代码：
  1. 首先输入呗。初始化pair数组。
  2. 然后排序。
  3. 在判断计数，这里要保存上面的结束时间，因为要判断下一个能不能用嘛。
  4. 看我代码~

AC代码 

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 3e4  +  2e3 +  7;
pair<int, int> info[MAX];
//全局变量区

bool cmp(const pair<int, int>& u, const pair<int, int>& v) {
    if (u.second == v.second) return u.first < v.first;
    return u.second < v.second;
}
//函数预定义区

int main() {
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        int len; cin >> info[i].first >> len;
        info[i].second = info[i].first + len;
    }
    sort(info + 1, info + 1 + n, cmp);
    int ans = 0, en = 0;
    for (int i = 1; i <= n; i++)
        if (en <= info[i].first) {
            ans++;
            en = info[i].second;
        }
    cout << ans << endl;
    return 0;
}
//函数区