题解：B4350 [信息与未来 2025] 美味水果

Yxa_Sheep · 2025-06-25 14:07:28 · 题解

upd 2025/6/28：修改了时间复杂度。

题目传送门

题意

过 x 天后这个水果的美味程度就开 x 次根号。有 n 个水果，求总的好吃程度的最大值。题目中说 1\le n\le 10^5，难到放这么久不会发霉吗？

思路

这道题很容易想到贪心，美味程度越大的水果开根号后损失的美味程度越多，所以美味程度越大的水果要越先吃掉，于是先把 a 数组从大到小排序，然后一个一个的吃掉。第 i 天吃掉的水果，放了 i-1 天，要开 i-1 次根号，于是有了这份代码：

sort(a + 1, a + n + 1, greater<int>()); //从大到小排序
for (int i = 1; i <= n; i++) //n 个水果
{
    for (int j = 1; j < i; j++) //开 i - 1 次根号
        a[i] = sqrt(a[i]); //sqrt 是开根号，需要头文件 cmath
    ans += a[i]; //加上这个水果的美味值 
}
printf("%d", ans); //输出总美味值

这样会超时三个点，40分。我们会发现 \sqrt{1} =1，如果 a_i 变成了 1 之后就可以跳出循环。a_i 最大为 10^9，开 5 次根号后可以变为1。（是不是一个水果放 5 天后就可以永久保存，美味程度始终为1）。时间复杂度最高的好像是快排，O(n \log{n})这是优化后的代码：

sort(a + 1, a + n + 1, greater<int>()); //从大到小排序
for (int i = 1; i <= n; i++) //n 个水果
{
    for (int j = 1; j < i && a[i] != 1; j++) //开 i - 1 次根号，并且这一项不为 1
        a[i] = sqrt(a[i]); //sqrt 是开根号，需要头文件 cmath
    ans += a[i]; //加上这个水果的美味值 
}
printf("%d", ans); //输出总美味值

完整代码

#include <bits/stdc++.h>
using namespace std;
int n, ans, a[100010];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1, greater<int>());
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < i && a[i] != 1; j++)
            a[i] = sqrt(a[i]);
        ans += a[i];
    }
    printf("%d", ans);
    return 0;
}

题解来之不易，且看且珍惜。给个赞再走吧。

题目传送门