题意无坑,不再赘述
这里题目暴力会超时,所以用STL,时间是O(nlogn),跑起来还是比较理想的
下面附几组数据
//171MS 3404K 732B C++ #include<stdio.h> #include <set> using namespace std; struct node{ int id,fi; node(){} node(int i ,int f):id(i),fi(f){} bool operator < (const node &a) const{ return a.fi>fi; } }a,temp,ans; set<node>ss; set<node>::iterator p; int main() { int n; while(scanf("%d",&n),n) { ss.clear(); ss.insert(node(1,1000000000));//插入第一个和尚 while(n--){ scanf("%d %d",&a.id,&a.fi); p=ss.upper_bound(a); ans=*p; if(p!=ss.begin()) { p--; temp=*p; if(ans.fi-a.fi>=a.fi-temp.fi) ans=temp; } printf("%d %d\n",a.id,ans.id); ss.insert(a); } } return 0; } /* 4 2 10 3 19 4 15 5 17 3 2 123 3 50 4 1234 6 2 500000 3 300 4 201 5 151 6 5000001 7 100 */