首页 > 代码库 > BZOJ1645 [Usaco2007 Open]City Horizon 城市地平线
BZOJ1645 [Usaco2007 Open]City Horizon 城市地平线
本来想打线段树的说。。。
就是把坐标离散化了，然后区间最大求和即可。。。
后来觉得有点烦的说（silver题就要线段树。。。），于是看了下usaco的题解，发现了个高端的东西：善用STL里的容器和迭代器就可以了。
以下就是高端程序：
1 /************************************************************** 2 Problem: 1645 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:264 ms 7 Memory:6120 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <vector>12 #include <utility>13 #include <map>14 #include <set>15 #include <algorithm>16 17 using namespace std;18 typedef pair<int, int> PAIR;19 typedef long long ll;20 21 map<int, vector<PAIR> > M;22 map<int, vector<PAIR> > ::iterator now;23 vector <PAIR> ::iterator I;24 multiset <int, greater<int> > S;25 ll ans;26 int n, L, R, H, K;27 28 inline int read(int &x){29 int sgn = 1; x = 0;30 char ch = getchar();31 while (ch < ‘0‘ || ch > ‘9‘){32 if (ch == ‘-‘) sgn = -1;33 ch = getchar();34 }35 while (ch >= ‘0‘ && ch <= ‘9‘){36 x = x * 10 + ch - ‘0‘;37 ch = getchar();38 }39 x *= sgn;40 }41 42 int main(){43 read(n);44 for (int i = 1; i <= n; ++i){45 read(L), read(R), read(H);46 M[L].push_back(make_pair(H, 1));47 M[R].push_back(make_pair(H, 0));48 }49 L = 0;50 for (now = M.begin(); now != M.end(); ++now){51 R = now -> first;52 if (!S.empty()) ans += (ll) (R - L) * (*S.begin());53 L = R;54 for (I = (now -> second).begin(); I != (now -> second).end(); ++I){55 K = I -> first;56 if (I -> second) S.insert(K);57 else S.erase(S.find(K));58 }59 }60 printf("%lld\n", ans);61 return 0;62 }
（反正蒟蒻自己是不会写的。。。真是太神了！！！）
BZOJ1645 [Usaco2007 Open]City Horizon 城市地平线
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。