题目描述

小明这天在参加公司团建，团建项目是爬山。在 x 轴上从左到右一共有 n座山，第 i 座山的高度为 hi。他们需要从左到右依次爬过所有的山，需要花费的体力值为 S = Σ(n,i=1)hi。
然而小明偷偷学了魔法，可以降低一些山的高度。他掌握两种魔法，第一种魔法可以将高度为 H 的山的高度变为 ⌊√H⌋，可以使用P次；第二种魔法可以将高度为H的山的高度变为 ⌊H/2⌋，可以使用Q次。并且对于每座山可以按任意顺序多次释放这两种魔法。
小明想合理规划在哪些山使用魔法，使得爬山花费的体力值最少。请问最优情况下需要花费的体力值是多少？

输入格式

输入共两行。
第一行为三个整数 n，P，Q。
第二行为 n 个整数 h1，h2，. . . ，hn。

输出格式

输出共一行，一个整数代表答案。

样例输入

4 1 1
4 5 6 49

样例输出

18

提示

【样例说明】
将第四座山变为 ⌊√49⌋ = 7，然后再将第四座山变为 ⌊7/2⌋ = 3。体力值为 4 + 5 + 6 + 3 = 18。

【评测用例规模与约定】

对于 20% 的评测用例，保证 n ≤ 8，P = 0。
对于 100% 的评测用例，保证 n ≤ 100000，0 ≤ P ≤ n，0 ≤ Q ≤ n，0 ≤ hi ≤ 100000。

优先队列(90%)

用优先队列/堆存储高度，每次都对当前最高的山进行判断，看那种操作会使山的高度尽可能小，优先使用开根

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, P, Q;
    long long ans = 0;
    priority_queue<int> h;
    cin >> n >> P >> Q;
    for (int i = 0; i < n; i++)
    {
        int hi;
        cin >> hi;
        h.push(hi);
    }
    while (P || Q)
    {
        //取出第一个数
        int first = h.top();
        h.pop();
        //对最高的山进行两种操作，哪种更矮就用哪种
        if (P && Q)
        {
            if (sqrt(first) <= first / 2)
            {
                h.push(sqrt(first));
                P--;
            }
            else
            {
                h.push(first / 2);
                Q--;
            }
        }
        //如果只剩一种魔法了，就直接用
        else if (P)
        {
            h.push(sqrt(first));
            P--;
        }
        else if (Q)
        {
            h.push(first / 2);
            Q--;
        }
    }
    while (!h.empty())
    {
        ans += h.top();
        h.pop();
    }
    cout << ans;
    return 0;
}

完美解(可能)

上面的想法本应该完美，但是这题hack了。
考虑如下输入
2 1 1 49 48
理所当然的，我们按上面操作得到
√49+48/2 = 7+24 =31
但理想结果应该是
49/2+√48 = 24+6 = 30
如果山的高度是实型，那我们上面的思路完全正确
但我们进行了向下取整，这导致了在某种情况下，我们应当对第最大的数进行除2操作
我们需要考虑大量极端数据，所以这题被hack了
通过观察，我们可以发现以上情况产生的原因是
49/2 = 48/2
√49 > √48
得出规律

n是奇数
n是完全平方数

考虑如下数据
4 2 1 49 48 1 1
如果对49除二的话得到
24 6 1 1
得到
4+6+1+1 = 12
实际应当先用完开根的次数
7 6 1 1
得到
3+6+1+1 = 11
我们发现出现上述情况也不能无脑进行除二
在操作次数足够时，仍应当以效果普遍更好的开根为主
再考虑如下数据
4 2 2 49 49 48 48
用优先队队列取出第二高的山是49，但实际应当是48
所以一次只能取一个数的优先队列并不能满足我们的需求
由上述考虑得到代码

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, p, q, i, max = 0;
    int h[100005] = {};
    long long ans = 0;
    cin >> n >> p >> q;
    for (i = 0; i < n; i++)
    {
        int hi;
        cin >> hi;
        h[hi]++;
        if (hi > max)
            max = hi;
    }
    // 从最高的山开始找
    i = max;
    // i是山的高度，h[i]是高度为i的山的个数
    while (i)
    {
        // 遍历最高的山
        while (h[i])
        {
            // 没有魔法次数就输出结果
            if (!p && !q)
            {
                for (int j = max; j > 0; j--)
                {
                    while (h[j]--)
                    {
                        ans += j;
                    }
                }
                cout << ans;
                return 0;
            }
            int sq = sqrt(i);
            // 有次数就尝试释放魔法
            if (p && q)
            {
                // 特判，i-1高度的山存在，是完全平方数，是奇数，且不能全部都用开根魔法，需要选择使用除二魔法
                if (h[i - 1] && sq * sq == i && i % 2 && h[i] + h[i - 1] > p)
                {
                    h[i]--;
                    h[i / 2]++;
                    q--;
                }
                // 正常情况，根据两种魔法的效果选择魔法释放
                else if (sq <= i / 2)
                {
                    h[i]--;
                    h[sq]++;
                    p--;
                }
                else
                {
                    h[i]--;
                    h[i / 2]++;
                    q--;
                }
            }
            // 只有一种魔法就把所有的魔法用完
            else if (p)
            {
                h[i]--;
                h[sq]++;
                p--;
            }
            else
            {
                h[i]--;
                h[i / 2]++;
                q--;
            }
        }
        // 高度为i的山都爬完了，找下一座山
        i--;
        // 更新最高的山的高度，可以不写
        max = i;
    }
    return 0;
}