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

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

题目传送门

题意

过

x

天后这个水果的美味程度就开

x

次根号。有

n

个水果，求总的好吃程度的最大值。题目中说

1\le n\le 10^5

，难到放这么久不会发霉吗？

思路

这道题很容易想到贪心，美味程度越大的水果开根号后损失的美味程度越多，所以美味程度越大的水果要越先吃掉，于是先把

a

数组从大到小排序，然后一个一个的吃掉。第

i

天吃掉的水果，放了

i-1

天，要开

i-1

次根号，于是有了这份代码：

CPP

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})

这是优化后的代码：

CPP

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); //输出总美味值

完整代码

CPP

#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;
}

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

题目传送门

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

文章操作

题意

思路

完整代码

相关推荐

评论

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