2024蓝桥杯每日一题（二分）

一、第一题：教室

解题思路：二分+差分
        对天数进行二分，在ck函数中用差分方法优化多次区间累加。

【Python程序代码】

n,m = map(int,input().split())
a = [0] + list(map(int,input().split()))
d,s,t = [0]*(m+5),[0]*(m+5),[0]*(m+5)
for i in range(1,m+1):d[i],s[i],t[i] = map(int,input().split())
l,r = 1,m+1
def ck(mid):tep = [0]*(n+5)for i in range(1,mid+1):tep[s[i]] += d[i]tep[t[i]+1] -= d[i]for i in range(1,n+1):tep[i] += tep[i-1]if tep[i]>a[i]:return Falsereturn True
while l<r:mid = (l+r+1)//2if ck(mid):l = midelse:r = mid-1if r>m:print(0)
else:print(-1)print(r)

 二、第二题：分巧克力

解题思路：二分
        对边长二分，所以每块大巧克力最多可以分成(h[i]/mid)*(w[i]/mid)。

【Python程序代码】

n,k = map(int,input().split())
h,w = [],[]
for i in range(n):a,b = map(int,input().split())h.append(a); w.append(b)
l,r = 1,100000
def ck(mid):res = 0for i in range(n):res += (h[i]//mid)*(w[i]//mid)if res>=k:return Truereturn False
while l<r:mid = (l+r+1)//2if ck(mid):l = midelse:r = mid-1
print(r)

三、第三题： 管道

 解题思路：二分+区间合并
        对时间进行二分，然后在ck函数中使用区间合并进行优化。下面程序貌似没AC.

【Python程序代码】

n,L = map(int,input().split())
sl = [[0,0]for i in range(n)]
tp = [[0,0]for i in range(n)]
for i in range(n):sl[i][0],sl[i][1] = map(int,input().split())
def cmp(x):return (x[0],x[1])
sl.sort(key=cmp)
l,r = 1,1000000000
def ck(mid):mi,ma = 2,L-1for i in range(n):if mid>=sl[i][1]:tp[i][0] = sl[i][0] - (mid-sl[i][1])tp[i][1] = sl[i][0] + (mid-sl[i][1])if tp[i][0]<mi:mi=tp[i][0]if tp[i][1]>ma:ma=tp[i][1]else:tp[i][0]=tp[i][1]=0if mi>1 or ma<L:return Falsetp.sort(key=cmp)ll = 0for i in range(n):if tp[i][0]==tp[i][1]==0:continueelse:if tp[i][0]>ll+1:return Falsell = max(ll,tp[i][1])if ll>=L:return Truereturn Falsewhile l<r:mid = (l+r)//2if ck(mid):r=midelse:l=mid+1
print(r)

四、第四题： 技能升级

 解题思路：二分
        对攻击力大小进行二分，题的本质考的是多路归并，采用二分进行优化。

【Python程序代码】

n,m = map(int,input().split())
a,b = [],[]
for i in range(n):a_,b_ = map(int,input().split())a.append(a_); b.append(b_)
l,r = 0,10000000def ck(mid):res = 0for i in range(n):if a[i]<mid:continueres += (a[i]-mid)//b[i] + 1if res>=m:return Truereturn False
while l<r:mid = (l+r+1)>>1if ck(mid):l = midelse:r = mid-1
cnt,res=m,0
for i in range(n):if a[i]<r:continuet = (a[i]-r)//b[i] +1cnt -= tres += (2*a[i]-(t-1)*b[i])*t//2
print(res+cnt*r)

五、第五题： 冶炼金属

 解题思路：二分
        对V值进行二分，分别找左右边界。

【Python程序代码】

n = int(input())
a,b = [0]*(n+5),[0]*(n+5)
for i in range(n):a[i],b[i] = map(int,input().split())
def pd1(x):for i in range(n):t = a[i]//xif t>b[i]:return Falseif t<b[i]:return Truereturn True
def pd2(x):for i in range(n):t = a[i]//xif t>b[i]:return Trueif t<b[i]:return Falsereturn True
def solve():l,r = 1,1000000000while l<r:mid = (l+r)//2if pd1(mid):r=midelse:l=mid+1res1 = rl, r = 1, 1000000000while l < r:mid = (l + r + 1) // 2if pd2(mid):l = midelse:r = mid - 1res2 = rprint(res1,res2)
solve()