头像

accessy




离线:15小时前


最近来访(6)
用户头像
Mr.Li
用户头像
kaluli7711
用户头像
acwing_4869
用户头像
PHarr
用户头像
AC摆渡人

活动打卡代码 AcWing 790. 数的三次方根

accessy
15小时前

n为小数时,立方根>n,所以在-n,n找不到答案

def check(mid):
    if mid**3>x: return True
    else: return False

def bsearch3(l,r):
    c=10**-8
    while r-l>c:
        mid=(l+r)/2
        if check(mid): r=mid
        else: l=mid
    return l

x=float(input())

ans=bsearch3(-1000,1000)
print('{:.6f}'.format(ans))


活动打卡代码 AcWing 789. 数的范围

accessy
17小时前
def check1(x,y):
    if x<=y: return True
    else: return False
def check2(x,y):
    if x>=y: return True
    else: return False
def bsearch1(l,r,x):
    while l<r:
        mid=l+r+1>>1
        if check1(q[mid],x): l=mid
        else: r=mid-1
    return l
def bsearch2(l,r,x):
    while l<r:
        mid=l+r>>1
        if check2(q[mid],x): r=mid
        else: l=mid+1
    return l


n,k=map(int,input().split())
q=[int(i) for i in input().split()]

while k:
    x=int(input())
    start,end=bsearch2(0,len(q)-1,x),bsearch1(0,len(q)-1,x)
    if q[start]!=x:
        start=end=-1
    print(start,end)

    k-=1


活动打卡代码 AcWing 788. 逆序对的数量

accessy
18小时前
tmp=[]
def merge_sort(q,l,r):
    if l>=r:
        return 

    mid=(l+r)//2
    merge_sort(q,l,mid)
    merge_sort(q,mid+1,r)

    global tmp; tmp=[]
    i,j=l,mid+1
    while i<=mid and j<=r:
        if q[i]<=q[j]:
            tmp+=[q[i]]
            i+=1
        else:
            tmp+=[q[j]]
            j+=1
            global cnt; cnt+=mid-i+1
    tmp+=q[i:mid+1]
    tmp+=q[j:r+1]
    q[l:r+1]=tmp

n=int(input())
q=[int(i) for i in input().split()]

cnt=0
merge_sort(q,0,len(q)-1)

print(cnt)


活动打卡代码 AcWing 786. 第k个数

accessy
20小时前
def quick_sort(q,l,r):
    if l>=r:
        return
    i=l-1;j=r+1;x=q[(l+r)//2]
    while i<j:
        i+=1;j-=1
        while q[i]<x: i+=1
        while q[j]>x: j-=1
        if i<j:
            q[i],q[j]=q[j],q[i]
    quick_sort(q,l,j)
    quick_sort(q,j+1,r)

n,k=input().split()
q=[int(i) for i in input().split()]
quick_sort(q,0,len(q)-1)

print(q[int(k)-1])


活动打卡代码 AcWing 787. 归并排序

accessy
20小时前
tmp=[]
def merge_sort(q,l,r):
    if l>=r:
        return

    mid = (l+r)//2
    merge_sort(q,l,mid)
    merge_sort(q,mid+1,r)

    global tmp; tmp=[];
    i,j=l,mid+1
    while i<=mid and j<=r:
        if q[i]<=q[j]:
            tmp+=[q[i]]
            i+=1
        else:
            tmp+=[q[j]]
            j+=1
    tmp+=q[i:mid+1]
    tmp+=q[j:r+1]  
    q[l:r+1]=tmp

n=int(input())
q=[int(i) for i in input().split()]
merge_sort(q,0,len(q)-1)

for i in q:
    print(i,end=' ')



活动打卡代码 AcWing 786. 第k个数

accessy
20小时前
tmp=[]
def merge_sort(q,l,r):
    if l>=r:
        return

    mid = (l+r)//2
    merge_sort(q,l,mid)
    merge_sort(q,mid+1,r)

    global tmp
    tmp=[]; i,j=l,mid+1
    while i<=mid and j<=r:
        if q[i]<=q[j]:
            tmp+=[q[i]]
            i+=1
        else:
            tmp+=[q[j]]
            j+=1

    if i<=mid: tmp+=q[i:mid+1]
    if j<=r: tmp+=q[j:r+1]

    j=0
    for i in range(l,r+1):
        q[i]=tmp[j]
        j+=1

n=int(input())
q=[int(i) for i in input().split()]
merge_sort(q,0,len(q)-1)

for i in q:
    print(i,end=' ')



活动打卡代码 AcWing 785. 快速排序

accessy
1天前
因为pyhon没有do while结构,所以只能用while实现

写法一:用while True if break 直接模拟do while
def quick_sort(q,l,r):
    if l>=r:
        return

    i=l-1; j=r+1; x=q[(l+r)//2]
    while i<j:
        while 1:
            i=i+1
            if q[i]>=x:
                break
        while 1:
            j=j-1
            if q[j]<=x:
                break
        if i<j:
            q[i],q[j]=q[j],q[i]
    quick_sort(q,l,j)
    quick_sort(q,j+1,r)

q=[int(i) for i in input().split()]
quick_sort(q,0,len(q)-1)

for i in range(len(q)):
    print(q[i],end=' ')

写法二:改成先while判断,再执行i+=1;j-=1。但为了与do while 逻辑上等效,while外需先执行一次i+=1;j-=1
def quick_sort2(q,l,r):
    if l>=r:
        return

    i=l-1; j=r+1; x=q[(l+r)//2]
    while i<j:
        i+=1; j-=1
        while q[i]<x: i+=1
        while q[j]>x: j-=1
        if i<j:
            q[i],q[j]=q[j],q[i]

    quick_sort2(q,l,j)
    quick_sort2(q,j+1,r)    




accessy
4天前

AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/42349/




accessy
4天前

AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/42349/