切长条 贪心

切长条

题目大意：

解题思路：
贪心就完事了，把长条按最右端从小到大排序，每次使没被切过的长条最右端为判断点即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
struct p {
    ll L, R;//左边和右边
} a[N];
bool cmp(p a, p b) {
    if (a.R != b.R) return a.R < b.R;
    return a.L < b.L;
}
int main() {
    ll n, l, ans = 1;//至少肯定有一刀
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i].L >> l, a[i].R = a[i].L + l;
    sort(a, a + n, cmp);
    for (ll i = 1, p = a[0].R; i < n; ++i)
        if (a[i].L >= p) p = a[i].R, ++ans;
    cout << ans << endl;
    return 0;
}

Code：