AW136 邻值查找 （【模板】set）

题目地址

---

注意点：

• 由贪心可知，仅需要从较大值和较小值中选择，delta相同时优先选择较小值即可.

---

#include<cstdio>
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
const int INF=2e9;
set<pair<int,int> > basicSet;//数值存储器

int main(){
	int n;
	scanf("%d",&n);
	int val1;//第一个值
	scanf("%d",&val1);
	basicSet.insert(make_pair(val1,1));
	for(int i=2;i<=n;i++){
		int tmp;
		scanf("%d",&tmp);
		basicSet.insert(make_pair(tmp,i));
		//获取最小值j，选择A_j较小的那个
		//输出最小值点
		set<pair<int,int> >::iterator it=basicSet.find(make_pair(tmp,i));//获取迭代器
		pair<int,int> ans;//答案(first:差值 second:位置)
		ans.first=INF;
		if(++it!=basicSet.end()){
			ans.first=(*it).first-tmp;
			ans.second=(*it).second;
		}
		it=basicSet.find(make_pair(tmp,i));//重置迭代器
		//使用迭代器获得前面的较好值
		if(it--!=basicSet.begin()&&ans.first>=tmp-(*it).first){//能更新
			ans.first=tmp-(*it).first;
			ans.second=(*it).second;
		}
		//输出答案
		printf("%d %d\n",ans.first,ans.second);
	}
	return 0;
}