NC25136 切长条 贪心

链接：https://ac.nowcoder.com/acm/problem/25136
来源：牛客网

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

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

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.

示例1
输入
复制

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

输出
复制

2

贪心,把每个区间按结束端点排序,如果某两个区间发生了没有交点的情况,则一定要多加一刀

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif


#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)
void err() { cout << "\033[39;0m" << endl; }
#endif

template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

int n, m, Q, K;
typedef pair<int,int> pii;
pii a[MAXN];

bool cmp(pii& x, pii& y) {
	return x.second == y.second ? x.first < y.first : x.second < y.second;
}

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	scanf("%d ", &n);
	//第二个数字指的是长度,而不是右端点
	for(int i=1; i<=n; i++)
		scanf("%d %d ", &a[i].first, &a[i].second), a[i].second+=a[i].first;
	int ans = 0, lst = -1;
	sort(a+1, a+1+n, cmp);
	for(int i=1; i<=n; i++) {
		if(lst <= a[i].first) { //注意等于的情况
			//发现上一刀无法切到这个矩形,就多来一刀ans++
			ans ++;
			lst = a[i].second;
		}
	}
	printf("%d\n", ans);

#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}