专栏文章

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

llizeyuhello
B4350题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip1irx8
此快照首次捕获于
2025/12/03 04:38
3 个月前
此快照最后确认于
2025/12/03 04:38
3 个月前
查看原文
赛时十几分钟 A 了，来写篇题解。

题意

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

题解

排序后暴力的时间复杂度为 O(n2)\mathcal{O}(n^{2})，只能拿到 3030 分。
观察数据，得出 aia_i 最大 10910^{9} 求 55 次平方根取整就会得到 11，而 1=1\sqrt{1} = 1，也就是说，ai=1a_i = 1 时对答案的贡献不再改变。
考虑贪心，将 aa 排序后，计算前 66 个数，其它数都为 11。
这种方法的时间复杂度为 O(nlog⁡n)\mathcal{O}(n \log n)，瓶颈在排序。

代码

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

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...