2-09 833 views
简单题。用set来做的话 还是比较简单的。
因为set是一个集合。 所以存在一个问题往集合内存 1 1两个相同的数的时候。会只能存上一个。
所以用一个数组来标记某个元素的个数。 当个数大于1的时候 数组内个数减一 否则 直接从集合内部删除这个数就好了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<iostream> #include<vector> #include<cmath> #include<map> #include<algorithm> #include<cstring> #include<cstdio> #include<cstdlib> #include<queue> #include<cmath> #include<set> #include<string> #include <stack> #define INF 1000000005 #define LL long long #define MAXN 1000000+10 #define debug() printf("...\n"); using namespace std; int a[MAXN]; int main (){ int n; while(scanf("%d",&n) && n){ LL sum = 0; set <int> q; memset(a,0,sizeof(a)); for(int i = 0; i < n; i++){ int k; scanf("%d",&k); for(int j = 0; j < k; j++){ int x; scanf("%d",&x); if(q.count(x)) a[x] ++; else q.insert(x); } set <int> ::iterator begin_ = q.begin(); set <int> ::iterator end_ = --q.end(); sum += (*end_) - (*begin_); if(a[*(end_)]) a[*(end_)]--; else q.erase(end_); if(a[*begin_]) a[*begin_]--; else q.erase(begin_); } cout << sum << endl; } return 0; } |
发现自己写的麻烦了。 去看了一下 还有一种以前没用过的神器multiset。。
multiset 和 set 差不多 区别就是 multiset 是允许有相同元素的存在的。。
那直接写就比较好了。
