首页 > 代码库 > UVA 11136 Hoax or what (multiset)

UVA 11136 Hoax or what (multiset)

题目大意:

超时进行促销,把账单放入一个箱子里

每次拿取数额最大的和最小的,给出 最大-最小  的钱。

问n天总共要给出多少钱。


思路分析:

multiset 上直接进行模拟

注意要使用long long 

而且multiset的删除要用 迭代器。


#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <set>
#define maxn 111111
using namespace std;

multiset<int>tab;
multiset<int>::iterator it;

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF && n)
    {
        tab.clear();

        long long ans=0;
        for(int i=0;i<n;i++)
        {
            int k;
            scanf("%d",&k);
            while(k--)
            {
                int a;
                scanf("%d",&a);
                tab.insert(a);
            }

            if(tab.size()==0)continue;
            it=tab.begin();
            int ans1=(*it);

            it=((tab.end()));
            it--;
            int ans2=(*it);

            ans+=(ans2-ans1);

            tab.erase(it);
            if(tab.size()>0)tab.erase(tab.begin());
        }
        printf("%lld\n",ans);
    }
    return 0;
}