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规模的数据。
你只需要做以下修改:
- 删掉自己写的
bubble_sort、bubble_pass、swap函数,替换成一个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; }
- 在
main函数里,把调用bubble_sort的那一行换成:
qsort(price, n, sizeof(long), compare);
这样修改后,你的程序运行速度会提升几个数量级,肯定能通过时间限制。
另外再确认下你的calc_min_price函数:逻辑完全正确,遍历排序后的数组,每三个元素跳过第三个(索引i满足i%3==2的元素),正好对应每组里免费的最便宜的那本书,这个计算没问题。
如果你不想用标准库函数,也可以自己实现归并排序或者快速排序,但qsort是经过高度优化的,直接用它最省心。
备注:内容来源于stack exchange,提问作者mendax1234




