---
tags: python, TOI, 二分搜
---

# ZJ f815. TOI_y21m4_a01遊戲升等
[ZJ f815](https://zerojudge.tw/ShowProblem?problemid=f815)

nlist:(1<=ni<=10^7)代表n個士兵目前的等級
nlist.sort()排序後，用第一次二分搜找最小nlist[lft=rgt]滿足cost>c
若第一次二分搜沒找到剛好已知的ni滿足cost=c的升級點，則須再利用找到的位置區間(lft-1,rgt)進行第二次二分搜
或最大的ni仍無法滿足cost>c，則從最大ni逐一+1找
仍是檢查最小cost>c的位置，然後ans = 該位置-1

## code
AC (55ms, 5.7MB)

# 2021	4	f815: TOI_y21m4_a01遊戲升等
# 可能需要兩次二分搜
# 第一次先找nlist(排序)中最小nlist[rgt]滿足cost>=c
# 若某個nlist滿足cost==c，則ans=nlist[mid],break結束
# 若第一次二分搜結果，最後一個nlist[n-1]也不滿足cost>=c，則須從最後一個nlist逐一+1找滿足的ans
# 若需要第二次二分搜，從nlist[lft]+1,+2,+3...nlist[rgt]二分搜找最小滿足cost>=c

n,c = map(int,input().split())
nlist = [int(x) for x in input().split()]
nlist.sort()
lft = 0
rgt = n
ans = 0
while lft<rgt:
    mid = (lft+rgt) // 2
    cost = 0
    for i in range(mid):
        cost +=(nlist[mid]-nlist[i])**2
    if cost==c:
        ans=nlist[mid]  #某個nlist剛好滿足，則ans已得，跳出
        break
    elif cost>c:
        rgt = mid
    else:
        lft = mid+1
    # print(lft,rgt)
# print(lft,rgt,ans)

if not ans:
    if lft==n: # 若第一次二分搜結果，最後一個nlist[n-1]也不滿足cost>=c，則須從最後一個nlist[-1]+1逐一找找滿足cost>=c的ans
        cost=0
        ans = nlist[-1]+1
        while cost<c:
            cost = 0
            for i in range(n):
                cost +=(ans-nlist[i])**2        
            ans +=1
        ans -=1
    else:
        lftn = nlist[lft-1]
        rgtn = nlist[rgt]
        while lftn<rgtn:
            mid = (lftn+rgtn) // 2
            cost = 0
            for i in range(lft):
                cost +=(mid-nlist[i])**2
            if cost==c:
                ans = mid
                break
            elif cost>c:
                rgtn = mid
            else:
                lftn = mid+1
        # print(lftn,rgtn)
        if not ans: ans = lftn-1
print(ans)