首页 > 代码库 > HNOI2002 营业额统计 平衡查找树
HNOI2002 营业额统计 平衡查找树
先用set 撸了一发
1 // File Name: first.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月15日 星期二 19时41分13秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #include<climits>25 #include<queue>26 27 using namespace std;28 29 int main(){30 31 long long n ; 32 while(scanf("%lld",&n) != EOF)33 {34 long long x; 35 set<long long>a;36 set<long long>::iterator l,en,be;37 set<long long>::iterator r;38 long long sum = 0 ;39 scanf("%lld",&x);40 sum += x;41 a.insert(x);42 for(int i = 2;i <= n;i ++)43 {44 scanf("%lld",&x);45 if(a.find(x) != a.end()) continue;46 47 a.insert(x);48 en = a.end();49 --en;50 if(a.find(x) == en)51 {52 l = a.find(x);53 --l ; 54 // printf("**%lld\n",*l);55 sum += x - *l;56 }else if(a.find(x) == a.begin()){57 l = a.find(x);58 ++l ; 59 sum += *l -x;60 // printf("**%lld\n",*l);61 }else {62 l = a.find(x);63 r = a.find(x);64 r = ++r;65 l = --l;66 // printf("**%lld %lld\n",*l,*r);67 sum += min(x-*l,*r-x);68 }69 70 }71 printf("%lld\n",sum);72 }73 74 return 0;75 }
测试数据 #1: Accepted, time=20ms, mem=1256KB, score=10
测试数据 #2: Accepted, time=0ms, mem=640KB, score=10
测试数据 #3: Accepted, time=0ms, mem=636KB, score=10
测试数据 #4: Accepted, time=10ms, mem=956KB, score=10
测试数据 #5: Accepted, time=30ms, mem=1996KB, score=10
测试数据 #6: Accepted, time=20ms, mem=1964KB, score=10
测试数据 #7: Accepted, time=20ms, mem=1620KB, score=10
测试数据 #8: Accepted, time=20ms, mem=1620KB, score=10
测试数据 #9: Accepted, time=20ms, mem=1244KB, score=10
测试数据 #10: Accepted, time=0ms, mem=640KB, score=10
Time = 140ms Mem = 1996KB Score= 100
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。