一般解法:先排序一次,然后重复r次:两两比较,把赢的人得分+1,最后排序。
代码:
时间复杂度:O(nlogn * r) (实际上n代表2n,但常数项省略)
最高运行时间:700ms左右✔(由于数组重复元素较多所以建议用stable_sort可以控制在600ms以下)
但是你放进洛谷里测:怎么两个TLE啊啊啊啊啊啊谁设的500ms啊啊啊啊啊啊啊
有没有优化的方法???
答案是肯定的!!!
我们仔细思考🤔:首先这个序列排序后得分是有序的,如果按顺序把赢了的和输了的分开是不是也是有序的?
举个例子:
是不是有序的?
如果你怀疑的话,你可以多实验几次(
然后我们把赢了的队员全部加1分(实际上在进行分输赢时就可以加),由于加的数值是相同的,所以就算加一亿分都是有序(不考虑爆int)
知道了这个,接着怎么做?
归并排序学过吗?
没学过也不用担心!网上搜
其中最终要的一步之一好吧本身也就只有两步就是“并”
所谓并,就是把两个有序数组合并成一个
具体过程:把最前面的元素进行比较,哪个小(大)就拿哪个,然后进行下一轮比较
懂了吗?本来归并排序还有归的操作,是为了原来的无序数组要划分成无数个有序数组来合并
但是——因为只有两个有序数组需要排序,所以省去了很多小并,只剩下了一个大并(
一次大并的时间复杂度为O(n),按照题目重复r次,所以本题解时间复杂度就为O(n * r)了
废话不多说,下↓
时间复杂度:O(n * r)
最高运行时间:147ms😎
不要CV球球了啊啊啊啊啊主要了解思路
看到了点个赞呗,第一次写这么长的题解qwq