uva 11136
用两个优先队列来实现，因为队列只能从一头出去；
所以维护一个数组，来标记这个队列的已经出列而另外一个队列没有出列的元素；
到时候再把他们删了就行；
1 #include<cstdio> 2 #include<queue> 3 #include<cstring> 4 #define maxn 1000009 5 using namespace std; 6 7 priority_queue<int,vector<int>,greater<int> >gq; 8 priority_queue<int,vector<int>,less<int> >lq; 9 int numg[maxn],numl[maxn]; 10 int main() 11 { 12 int n,x,k; 13 while(scanf("%d",&n)&&n) 14 { 15 memset(numl,0,sizeof numl); 16 memset(numg,0,sizeof numg); 17 long long ans=0; 18 while(!gq.empty())gq.pop(); 19 while(!lq.empty())lq.pop(); 20 for(int i=0;i<n;i++) 21 { 22 scanf("%d",&k); 23 while(k--) 24 { 25 scanf("%d",&x); 26 gq.push(x); 27 lq.push(x); 28 } 29 while(1) 30 { 31 if(numg[lq.top()]>0) 32 { 33 numg[lq.top()]--; 34 lq.pop(); 35 } 36 else break; 37 } 38 while(1) 39 { 40 if(numl[gq.top()]>0) 41 { 42 numl[gq.top()]--; 43 gq.pop(); 44 } 45 else break; 46 } 47 numg[gq.top()]++; 48 numl[lq.top()]++; 49 ans+=lq.top()-gq.top(); 50 gq.pop(); 51 lq.pop(); 52 } 53 printf("%lld ",ans); 54 } 55 return 0; 56 }
还可以用multiset来做；
代码：
1 #include<cstdio> 2 #include<set> 3 using namespace std; 4 5 multiset<int>s; 6 7 int main() 8 { 9 int n,k,x; 10 while(scanf("%d",&n)&&n) 11 { 12 long long ans=0; 13 s.clear(); 14 while(n--) 15 { 16 scanf("%d",&k); 17 while(k--) 18 { 19 scanf("%d",&x); 20 s.insert(x); 21 } 22 multiset<int>::iterator it; 23 it=s.begin(); 24 int mi=*it; 25 s.erase(it); 26 it=s.end(); 27 it--; 28 int ma=*it; 29 s.erase(it); 30 ans+=ma-mi; 31 } 32 printf("%lld ",ans); 33 } 34 return 0; 35 }