hdu 4585 Shaolin(二分）

题目链接：hdu 4585 Shaolin

题目大意：在一个寺庙里有个和尚，序号为1，法力非常高，接下来会有n个和尚来到寺庙，每次有和尚来到寺庙，都会向寺庙中的和尚发起挑战，每行给出和尚的序号和法力，挑战的和尚会挑选寺庙中法力和自己最接近的，如果可以，还会挑法力比自己低的（即最近的情况有比自己高的和比自己低的），给出每个和尚做挑战和尚的序号。

解题思路：二分搜索，有set完成，每次注意特判一下是否有两个差值绝对值相等的情况。

#include <stdio.h>
#include <string.h>
#include <set>
#include <algorithm>
#include <stdlib.h>

using namespace std;
const int N = 1e5+5;
const int M = 5000005;

struct HS {
	int id, power;
}s[N];

int n, v[M];
set<int> vis;

void init () {

	vis.clear ();
	memset(v, 0, sizeof(v));

	for (int i = 0; i < n; i++) {
		scanf("%d%d", &s[i].id, &s[i].power);
		v[s[i].power] = s[i].id;
	}

	vis.insert(s[0].power);
}

int main () {
	while (scanf("%d", &n) == 1 && n) {
		init ();

		printf("%d 1\n", s[0].id);

		for (int i = 1; i < n; i++) {
			int ans, up, down;
			set<int>::iterator it = vis.lower_bound(s[i].power);

			up = *it;

			if (it != vis.begin())
				it--;

			down = *it;

			if (abs(down - s[i].power) <= abs(up - s[i].power))
				ans = down;
			else
				ans = up;

			printf("%d %d\n", s[i].id, v[ans]);
			vis.insert(s[i].power);
		}
	}
	return 0;
}