首页 > 代码库 > hdu--4585--lower_bound()

hdu--4585--lower_bound()

2024-07-29 08:45:26   222人阅读

好久不见     lower_bound()

最近 事情太多了 龙兄 来了宁波 我们几个一起陪他玩了几天 那几天就没碰过题了 昨天他回临安了 明年应该就是我们宁波这3个 过去找他了

我们 设计了很多创业大计 描绘了美好的蓝图 就差 资金到位了 哈哈~~

-------

这题的话 就是开始给你一个人的ID与他的能力值  起初这个集合中只有 一个人：Id 1  能力值 1000000000

后来 每次加入一个人的时候 总是要从这个集合中 找出一个人与他进行PK 这个人的能力值要与他是得到这样的关系min( abs(new-old) )因为这是绝对值得 所以如果存在上界与下界同时满足 取下界 即小于<new的值  

这样每次插入一个 输出一个 最后就可以了

但是我的代码 运行时间好tm长啊 要900+ms 一共给的时间也就1000ms 我也是 醉了

顺便 提下lower_bound(var)函数是返回一个序列中大于等于var的第一个位置  注意这是一个前闭后开的区间 所以如果这个var大于这个序列的所有元素 那么返回的将是一个没有元素的位置 即xx.end()

 1 #include <iostream> 2 #include <map> 3 using namespace std; 4  5 map<int,int>mp; 6  7 int main() 8 { 9     cin.sync_with_stdio(false);10     int n , Id , grade , var , num;11     while( cin >> n && n )12     {13         mp.clear( );14         map<int,int>::iterator ans;15         mp[1000000000] = 1;16         for( int i = 0 ; i<n ; ++i )17         {18             cin >> Id >> grade;19             if( !i )20             {21                 cout << Id << " " << 1 << endl;22             }23             else24             {25                 ans = mp.lower_bound( grade );26                 if( ans == mp.begin() )27                     cout << Id << " " << ans->second << endl;28                 else29                 {30                     var = ans->first;31                     num = ans->second;32                     --ans;33                     if( var-grade < grade-(ans->first) )34                         cout << Id << " " << num << endl;35                     else36                         cout << Id << " " << ans->second << endl;37                 }38             }39             mp[ grade ] = Id;40         }41     }42     return 0;43 }
View Code

 

today:　　

　　你说 谈恋爱需要靠什么呢？

　　我什么都不想罗列

　　最后反正是看脸

　　

 

hdu--4585--lower_bound()


联系
我们