首页 > 代码库 > 一个问题
一个问题
做题的时候碰到的,不太明白为什么。
题目:http://acm.hdu.edu.cn/showproblem.php?pid=4585
如果用我注释的写法就会超时,而我用注释上面的写法就会快很多,目前的猜测是set的lower_bound做了针对性的优化。。
1 #include<bits/stdc++.h> 2 using namespace std; 3 set<int> s; 4 map<int,int> mp; 5 int main(){ 6 int n; 7 while(scanf("%d",&n) && n){ 8 s.clear(); 9 mp.clear(); 10 s.insert(1000000000); 11 mp[1000000000] = 1; 12 int id,grade; 13 for(int i = 0;i<n;i++){ 14 scanf("%d%d",&id,&grade); 15 16 set<int>::iterator it1 = s.lower_bound(grade),it2; 17 //这样写不知道为什么会超时 18 //set<int>::iterator it1,it2; 19 //it1 = lower_bound(s.begin(),s.end(),grade); 20 if(it1 == s.begin()){ 21 printf("%d %d\n",id,mp[*it1]); 22 s.insert(grade); 23 mp[grade] = id; 24 continue; 25 } 26 it2 = it1; 27 it1--; 28 if(it2 == s.end()){ 29 printf("%d %d\n",id,mp[*it1]); 30 }else if(grade-*it1 <= *it2-grade){ 31 printf("%d %d\n",id,mp[*it1]); 32 }else{ 33 printf("%d %d\n",id,mp[*it2]); 34 } 35 s.insert(grade); 36 mp[grade] = id; 37 } 38 } 39 return 0; 40 }
一个问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。