首页 > 代码库 > [HDU 4585] Shaolin (map应用)
[HDU 4585] Shaolin (map应用)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4585
题目大意：不停的插入数字，问你跟他相距近的ID号。如果有两个距离相近的话选择小的那个。
用map，先用upper_bound找到大的，然后迭代器减1，就能够找到相近的两个。
然后。。用链表不知道为什么有问题。。。。
而且迭代器it，如果减1的话，不能写 it2 = --it1; 这样会wa
但是。。it2 = it1; it2--;这样就AC了，在这里记录一下，今后注意。
1 //#pragma comment( linker, "/STACK:1024000000,1024000000") 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <algorithm> 6 #include <cmath> 7 #include <map> 8 #include <iterator> 9 using namespace std;10 11 typedef map<int,int>::iterator pt;12 13 map<int,int> mp;14 int n;15 16 int main(){17 while(scanf("%d",&n),n){18 int k,g;19 mp.clear();20 mp.insert(make_pair(1000000000,1));21 for(int i=0;i<n;i++){22 scanf("%d%d",&k,&g);23 pt it2 = mp.upper_bound(g);24 25 if( it2==mp.begin() ){26 printf("%d %d\n",k,it2->second);27 mp.insert(make_pair(g,k));28 continue;29 }30 31 pt it1 = it2;32 it1--;33 if( abs(g-it1->first)<=abs(g-it2->first) ) {34 printf("%d %d\n",k,it1->second);35 } else {36 printf("%d %d\n",k,it2->second);37 }38 mp.insert(make_pair(g,k));39 }40 }41 return 0;42 }
[HDU 4585] Shaolin (map应用)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。