记录编号	156799	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题A	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.185 s
提交时间	2015-04-06 11:50:22	内存使用	2.58 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define getc() getchar() 
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 100003;
int N, f[maxn], val[maxn];
struct Seg{int l, r;}S[maxn], *end, seg[maxn], *sEnd = seg;
inline bool operator < (const Seg &a, const Seg &b){return a.r==b.r?a.l<b.l:a.r<b.r;}
inline bool operator == (const Seg &a, const Seg &b){return a.r == b.r && a.l == b.l;}
inline void init(){
	getd(N);
	int b, t;
	Seg *it = S, *first = S;int *itv = val;end = S + N;
	for(;it != end;++it){
		getd(it->l), getd(b);
		it->r = N - b;
	}
	end->l = N + 1, end->r = N + 1;
	sort(S, end);
	it = S + 1;
	while(first != end){
		while(*it == *first)++it;
		b = it - first;
		if((t = first->r - first->l) > 0){
			sEnd->l = first->l, sEnd->r = first->r, *itv = min(t, b);
			++sEnd;++itv;
		}
		first = it++;
	}
}
inline void work(){
	int i, last = 0, n = sEnd - seg;
	*f = *val;
	for(i = 1;i < n;++i){
		f[i] = f[i-1];
		while(seg[last].r <= seg[i].l)++last;
		if(last)f[i] = max(f[i], f[last-1] + val[i]);
	}
	printf("%d\n", N - f[n-1]);
}
int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(a);
#endif
	init();
	work();

#ifdef DEBUG
	printf("\n%lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}