http://codevs.cn/problem/1285/

題解：

運用STL的set，和算法庫(Algorithm)的upper_bound()與lower_bound()，實現(xiàn)log(n)的查找。要注意的是set類的upper_bound(x) 返回在集合中第一個大于x的元素，而lower_bound()返回在集合中第一個大于或等于x的元素，與它們在數(shù)組中的作用不太一樣。

代碼：

總時間耗費: 657ms
總內(nèi)存耗費: 748B

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<set> #include<cmath> #include<algorithm> using namespace std;set<int> S; int main() {int n;bool flag;cin >> n;int ans = 0;for(int i = 1; i <= n; i++) {int a, b;cin >> a >> b;if(S.empty() || flag == a) {S.insert(b);flag = a;} else {set<int>::iterator it = S.lower_bound(b);int x = *it, y = (it == S.begin())? (*it) : *(--it);if(abs(b-x) <= abs(b-y)) S.erase(x); else S.erase(y);ans = (ans + min(abs(b-x), abs(b-y))) % 1000000;}}cout << ans << endl;return 0; }

---

總結(jié)

以上是生活随笔為你收集整理的[CODEVS 1285] 宠物收养所的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。