You need to enable JavaScript to run this app.
最新活动
大模型
产品
解决方案
定价
生态与合作
支持与服务
开发者
了解我们

Kattis题目Akcija:使用O(N²)排序算法导致超时的问题求助

Kattis题目Akcija:使用O(N²)排序算法导致超时的问题求助

嗨,你的问题根源确实出在冒泡排序上,而且是非常典型的时间复杂度不匹配问题。

咱们先理清楚:题目里N的上限是100000,冒泡排序的时间复杂度是O(n²),当n=1e5时,需要执行的操作次数大概是1e10次——这远远超过了程序在常规时间限制(1-2秒)内能处理的操作量(一般最多1e8次左右),所以超时是必然的。

不过好消息是,你的核心解题逻辑是完全正确的:把价格从高到低排序,然后每三个一组跳过第三个(也就是免费掉每组里最便宜的那本),这个思路没问题,只需要把排序部分换成高效的O(n log n)算法就行。

在C语言里,最省事且高效的办法是直接用标准库的qsort函数,它实现了优化的快速排序,时间复杂度稳定在O(n log n),完全能处理1e5规模的数据。

你只需要做以下修改:

  1. 删掉自己写的bubble_sortbubble_passswap函数,替换成一个qsort的比较函数:
int compare(const void *a, const void *b) {
    long val1 = *(const long*)a;
    long val2 = *(const long*)b;
    // 实现降序排序:如果val1更大,返回-1;更小返回1;相等返回0
    if (val1 > val2) return -1;
    if (val1 < val2) return 1;
    return 0;
}
  1. main函数里,把调用bubble_sort的那一行换成:
qsort(price, n, sizeof(long), compare);

这样修改后,你的程序运行速度会提升几个数量级,肯定能通过时间限制。

另外再确认下你的calc_min_price函数:逻辑完全正确,遍历排序后的数组,每三个元素跳过第三个(索引i满足i%3==2的元素),正好对应每组里免费的最便宜的那本书,这个计算没问题。

如果你不想用标准库函数,也可以自己实现归并排序或者快速排序,但qsort是经过高度优化的,直接用它最省心。

备注:内容来源于stack exchange,提问作者mendax1234

火山引擎 最新活动