uva 11136 - Hoax or what

用两个优先队列来实现，因为队列只能从一头出去；

所以维护一个数组，来标记这个队列的已经出列而另外一个队列没有出列的元素；

到时候再把他们删了就行；

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #define maxn 1000009

 using namespace std;

 priority_queue<int,vector<int>,greater<int> >gq;

 priority_queue<int,vector<int>,less<int> >lq;

 int numg[maxn],numl[maxn];

 int main()

 {

     int n,x,k;

     while(scanf("%d",&n)&&n)

     {

         memset(numl,,sizeof numl);

         memset(numg,,sizeof numg);

         long long ans=;

         while(!gq.empty())gq.pop();

         while(!lq.empty())lq.pop();

         for(int i=;i<n;i++)

         {

             scanf("%d",&k);

             while(k--)

             {

                 scanf("%d",&x);

                 gq.push(x);

                 lq.push(x);

             }

             while()

             {

                 if(numg[lq.top()]>)

                 {

                     numg[lq.top()]--;

                     lq.pop();

                 }

                 else break;

             }

             while()

             {

                 if(numl[gq.top()]>)

                 {

                     numl[gq.top()]--;

                     gq.pop();

                 }

                 else break;

             }

             numg[gq.top()]++;

             numl[lq.top()]++;

             ans+=lq.top()-gq.top();

             gq.pop();

             lq.pop();

         }

         printf("%lld\n",ans);

     }

     return ;

 }

还可以用multiset来做；

代码：

 #include<cstdio>

 #include<set>

 using namespace std;

 multiset<int>s;

 int main()

 {

     int n,k,x;

     while(scanf("%d",&n)&&n)

     {

         long long ans=;

         s.clear();

         while(n--)

         {

             scanf("%d",&k);

             while(k--)

             {

                 scanf("%d",&x);

                 s.insert(x);

             }

             multiset<int>::iterator it;

             it=s.begin();

             int mi=*it;

             s.erase(it);

             it=s.end();

             it--;

             int ma=*it;

             s.erase(it);

             ans+=ma-mi;

         }

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

uva 11136 - Hoax or what

最新文章

热门文章