hdu多校第六场1012 （hdu6645） Stay Real 假博弈，真贪心

题意：

给你一个小根堆，从根开始拿，拿走子节点被拿完后才可以拿走父节点，两个人依次拿，谁拿的节点总和大谁获胜，问你谁有必胜策略。

题解：

小根堆中，每个点的权值总是不小于父亲节点的权值。所以无论怎么取，先拿走的数一定 不小于后面拿走的数。 此时双方的最优策略就是：贪心选择能取的数字之中最大的数。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<string>

#include<stack>

#include<algorithm>

using namespace std;

#define INF 0x3f3f3f3f

#define MAXN 100000+50

#define MAXM 30000

#define ll long long

#define rep(i,n,m) for(int i=n;i<=m;++i)

#define mod 1000000000 + 7

#define mian main

#define mem(a, b) memset(a, b, sizeof a)

#ifndef ONLINE_JUDGE

#define dbg(x) cout << #x << "=" << x << endl;

#else

#define dbg(x)

#endif

inline int read()

{

    int x = , f = ;

    char ch = getchar();

    while (ch < '' || ch > '')

    {

        if (ch == '-')

            f = -;

        ch = getchar();

    }

    while (ch >= '' && ch <= '')

    {

        x =  * x + ch - '';

        ch = getchar();

    }

    return x * f;

}

inline ll readll()

{

    ll x = , f = ;

    char ch = getchar();

    while (ch < '' || ch > '')

    {

        if (ch == '-')

            f = -;

        ch = getchar();

    }

    while (ch >= '' && ch <= '')

    {

        x =  * x + ch - '';

        ch = getchar();

    }

    return x * f;

}

ll a[MAXN];

int main()

{

    int T = read();

    while (T--)

    {

        int n = read();

        ll sums = , sume = ;

        rep(i, , n) a[i] = readll();

        sort(a + , a + n + );

        for (int i = n; i >= ; i-=)

        {

            sums += a[i];

        }

        for (int i = n - ; i >= ; i -= )

        {

            sume += a[i];

        }

        printf("%lld %lld\n", sums, sume);

    }

    return ;

}