Python implementation of official selection sorting of Luogu question list

P1271 【 Deep base 9. example 1】 Election of Student Union

n,m=map(int,input().strip().split())
ls=[int(i) for i in input().strip().split()]
ls.sort()
for i in ls:
    print(i,end=" ")

P1177 【 Templates 】 Quick sort

N=int(input().strip())
ls=[int(i) for i in input().strip().split()]
ls.sort()
for i in ls:
    print(i,end=" ")

P1923 【 Deep base 9. example 4】 Please k Small number

import numpy as np
n, k = map(int, input().split())
arr = np.fromstring(input(), dtype = np.uint32, sep=' ')
arr.sort()
print(arr[k])

notes ：Python There seems to be no and C++ Medium nth_element() Functions with the same function , Only use sort() Sort first and then find the k The number of bits , because Python The default integer in is 64 Bit form , Therefore, sorting will result in the last two points MLE, So you have to use fromstring() Function int To numpy Unique in Library 32 A form of , Yes, the detection machine in Los Angeles has numpy.

P1059 [NOIP2006 Popularization group ] A clear random number

n=input()
ls1=[int(i) for i in input().strip().split()]
ls2=[i for i in set(ls1)]
ls2.sort()
print(len(ls2))
for i in ls2:
    print(i,end=" ")

P1781 Cosmic president

def hanshu(a,b):
    c,d=len(a),len(b)
    if c<d:
        return False
    if c>d:
        return True
    for i in range(c):
        e,f=int(a[i]),int(b[i])
        if e>f:
            return True
        if e<f:
            return False
n=int(input().strip())
i,j=None,None
for k in range(1,n+1):
    m=input().strip()
    if i==None:
        i,j=m,k
    else:
        if hanshu(m,i)==True:
            i,j=m,k
print(j)
print(i)

P2676 [USACO07DEC]Bookshelf B

N,B=map(int,input().strip().split())
ls=[]
for i in range(N):
    ls.append(int(input().strip()))
ls.sort(reverse=True)
cnt1=0
cnt2=0
while True:
    cnt1+=ls[cnt2]
    cnt2+=1
    if cnt1>=B:
        break
print(cnt2)

P1116 Carriage reorganization

a=int(input())
b=[]
while len(b)<a:
    b+=[int(i) for i in input().split()]
c=0
for d in range(a):
    for e in range(0, a-d-1):
        if b[e] > b[e+1] :
            b[e], b[e+1] = b[e+1], b[e]
            c=c+1
print(c)

notes ： The input of this problem is far from the general .

P1152 Happy jump

ls=[int(i) for i in input().strip().split()]
n,ls=ls[0],ls[1:]
ls1=[i for i in range(1,n)]
ls2=[]
for i in range(n-1):
    c=abs(ls[i]-ls[i+1])
    ls2.append(c)
ls2.sort()
if ls2==ls1:
    print("Jolly")
else:
    print("Not jolly")

P1068 [NOIP2009 Popularization group ] The score line is drawn

from math import floor
def hanshu(ls):
    x=len(ls)
    for i in range(x-1):
        for j in range(x-i-1):
            if ls[j][1]==ls[j+1][1]:
                if ls[j][0]>ls[j+1][0]:
                    ls[j],ls[j+1]=ls[j+1],ls[j]
    for i in ls:
        print(i[0],i[1])
n,m=map(int,input().strip().split())
ls=[]
for i in range(n):
    a,b=map(int,input().strip().split())
    ls.append([a,b])
ls=sorted(ls,key=lambda x:x[1],reverse=True)
x=floor(m*1.5)
a=ls[x-1][1]
b=x
sl=ls[:x]
for i in range(x,n):
    if ls[i][1]>=a:
        sl.append(ls[i])
        b+=1
    else:
        break
print(a,b)
ls=[]
for i in sl:
    if ls==[]:
        x=i[1]
    if i[1]==x:
        ls.append(i)
    else:
        hanshu(ls)
        x=i[1]
        ls=[i]
hanshu(ls)

notes ： Maybe I wrote it complicated . I originally had a very simple code , But it's a little overtime , Sobbing . This code , From a large list , Make a small list of the same scores , Then bubble sort the small list according to the registration number . Then output the elements of the small list in turn .

P5143 Scrambler

def hanshu(a,b,c):
    return pow(a**2+b**2+c**2,1/2)
N=int(input())
ls=[]
for i in range(N):
    a,b,c=map(int,input().strip().split())
    ls.append([a,b,c])
ls=sorted(ls,key=lambda x:x[2])
cnt=0
for i in range(N-1):
    cnt+=hanshu(ls[i+1][0]-ls[i][0],ls[i+1][1]-ls[i][1],ls[i+1][2]-ls[i][2])
print("%.3f"%(cnt))

P1104 Birthday

import datetime
x=datetime.date(1800,1,1)
n=int(input().strip())
ls=[]
for i in range(n):
    a,b,c,d=input().strip().split()
    b,c,d=int(b),int(c),int(d)
    y=datetime.date(b,c,d)
    z=(y-x).days
    if ls==[]:
        ls.append([z,a])
    else:
        for i in ls:
            if z>i[0]:
                j=ls.index(i)
                ls.insert(j,[z,a])
                break
        else:
            ls.append([z,a])
ls=ls[::-1]
for i in ls:
    print(i[1])

notes ： Go straight to a far time , Just find out the number of days from everyone's birthday to this era , There's no need to compare year, month and day next to each other .

P1012 [NOIP1998 Improvement group ] Spell numbers

def hanshu( list ,x,y):
    global sl
    if x==y:
        z=""
        for i in  list :
            z+=i
        sl.append(int(z))
    else:
        for i in range(x,y):
             list [x], list [i]= list [i], list [x]
            hanshu( list ,x+1,y)
             list [x], list [i]= list [i], list [x]
n=int(input().strip())
ls=input().strip().split()
sl=[]
hanshu(ls,0,n)
print(max(sl))

notes ： Recursively create all numbers , Find the maximum value directly