SSL1200_促销_桶

lzusa 发布于 2019-04-22 1 次阅读


题目大意

每天都有若干个消费,每次将所以消费中的最大值和最小值相减然后累加起来,删除当前最大值和最小值

思路

这题直接用桶水过
O(n3)

#include 
using namespace std;
int f[10000001];
int main()
{
    int n;long long ans=0;
    scanf("%d",&n);
    int max=0;
    for (int i=1;i<=n;i++)
    {
        int m;
        scanf("%d",&m);
        for (int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            if (x>max) max=x;
            f[x]++; 
        }
        int x=0,y=max;
        while (f[x]==0) x++;
        while (f[y]==0) y--;
        if (y<=x) continue;
        ans=ans+y-x;
        f[x]--;
        f[y]--;
    }
    printf("%I64d\n",ans);
}
]]>