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

lizeyuhello · 2025-06-25 08:29:29 · 题解

赛时十几分钟 A 了，来写篇题解。

题意

给定一个长度为 n 的数组 a，每次需要从中选取一个未被选过的数累加入答案，此时 a 中所有未选取的 a_i(1 \leq i \leq n) 全部更新为 \sqrt{a_i}，求答案的最大值。

题解

排序后暴力的时间复杂度为 \mathcal{O}(n^{2})，只能拿到 30 分。

观察数据，得出 a_i 最大 10^{9} 求 5 次平方根取整就会得到 1，而 \sqrt{1} = 1，也就是说，a_i = 1 时对答案的贡献不再改变。

考虑贪心，将 a 排序后，计算前 6 个数，其它数都为 1。

这种方法的时间复杂度为 \mathcal{O}(n \log n)，瓶颈在排序。

代码

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

const int N = 1e5 + 5;
int n, ans;
int a[N];

int calc(int x, int k)
{
    int res = x;
    for (int i = 1; i <= k; ++i) //计算 x 开根 k 次取整
        res = sqrt(res);
    return res;
}

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 <= 7; ++i)
        ans += calc(a[i], i - 1);
    ans += max(0, n - 7); //其它数都是 1，直接加入答案
    printf("%d\n", ans);
    return 0;
}