求助卡常Py3

P5740 【深基7.例9】最厉害的学生

xtracer @ 2021-02-19 16:45:42

RT,自己手写类和快排,结果才53ms,离目标50ms还有距离(后来我用找最大值卡了最优解)。有大佬能给出优化方案吗?本蒟蒻感激不尽!

附上代码:

import sys
class Work(object):
    class stu(object):
        def __init__(self,name,score):
            self.name=name
            self.score=score
            self.res=sum(score)
    def make_stu(self,name,score):
        return self.stu(name,score)
work=Work()
def stu_speedsort(a,l,r):
    i=l;j=r;mid=a[(l+r)//2].res;
    while i<=j:
        while a[i].res<mid:i+=1
        while a[j].res>mid:j-=1
        if i<=j:
            a[i],a[j]=a[j],a[i]
            i+=1;j-=1;
    if l<j:stu_speedsort(a,l,j)
    if i<r:stu_speedsort(a,i,r)
a=[]
n=int(input())
for i in range(0,n):
    s=input().split()
    a.append(work.make_stu(s[0],list(map(int,s[1:4]))))
stu_speedsort(a,0,len(a)-1)
a.reverse()
win=a[0]
print(win.name,win.score[0],win.score[1],win.score[2])
del work,Work,stu_speedsort,a,n,win
sys.exit()

by xtracer @ 2021-02-19 16:46:35

喜提本题最长解/yun


by tribool4_in @ 2021-02-19 16:48:31

c++快一些,为何不用(

竞赛有了C++,不卡常,不被杀


by konjacq @ 2021-02-19 16:49:56

@xtracer 那你桶排鸡排啊


by _caiji_ @ 2021-02-19 16:50:26

复杂度能优化成 O(n+n),即循环一次找最大值。


by xtracer @ 2021-02-19 16:53:00

@wangwls 闲得发慌用Py3写一发,之前用C++交过了


by 林聪 @ 2021-02-19 17:09:00

@xtracer 这题需要排序?


|