洛谷 题单 官方精选 排序 Python实现

目录

• • P1271 【深基9.例1】选举学生会
  • P1177 【模板】快速排序
  • P1923 【深基9.例4】求第 k 小的数
  • P1059 [NOIP2006 普及组] 明明的随机数
  • P1781 宇宙总统
  • P2676 [USACO07DEC]Bookshelf B
  • P1116 车厢重组
  • P1152 欢乐的跳
  • P1068 [NOIP2009 普及组] 分数线划定
  • P5143 攀爬者
  • P1104 生日
  • P1012 [NOIP1998 提高组] 拼数

P1271 【深基9.例1】选举学生会

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 【模板】快速排序

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

P1923 【深基9.例4】求第 k 小的数

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

注：Python 中好像没有和 C++ 中的 nth_element() 功能相同的函数, 只能使用 sort() 先排序后再查找第 k 位的数, 由于 Python 中的整数默认是 64 位形式的, 因此在排序时会导致最后两个点 MLE, 因此必须使用 fromstring() 函数把 int 转为 numpy 库中特有的 32 位形式，没错洛谷的检测机竟然有numpy。

P1059 [NOIP2006 普及组] 明明的随机数

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 宇宙总统

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 车厢重组

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)

注释：它这道题的输入离大普。

P1152 欢乐的跳

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 普及组] 分数线划定

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)

注释：可能是我写复杂了。我原本有一个很简单的代码，但是有一个点超时了啊，呜呜。这段代码，从一个大的列表中，分出相同分数的小列表，再对这个小列表按照报名号进行冒泡排序。然后依次输出这个小列表的元素。

P5143 攀爬者

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 生日

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])

注释：直接找一个很远的年代，找出每个人的生日距离这个年代的天数就好了，没必要挨着去比较年月日吧。

P1012 [NOIP1998 提高组] 拼数

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

注释：递归造出所有的数，直接找出最大的值