周赛笔记233

发布日期: 2021-03-21

更新日期: 2021-12-01

文章字数: 479

阅读时长: 2 分

一、最大升序子数组和

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        ans=[nums[0]]
        pre=nums[0]
        for i in range(1,len(nums)):
            if nums[i]>pre:
                ans[-1]+=nums[i]
            else:
                ans.append(nums[i])
            pre=nums[i]
            #print(pre,ans)
        return max(ans)

二、积压订单中的订单总数

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        buy,sell=[],[]
        for p,m,t in orders:
            if t==0:  #buy,
                while m and sell:
                    tmp=sell[0]
                    if tmp[0]>p: break
                    deal=min(m,tmp[1])
                    m-=deal
                    tmp[1]-=deal
                    if tmp[1]==0:
                        heapq.heappop(sell)
                if m: heapq.heappush(buy,[-p,m])
            else: #sell
                while m and buy:
                    tmp=buy[0]
                    if -tmp[0]<p: break
                    deal=min(m,tmp[1])
                    m-=deal
                    tmp[1]-=deal
                    if tmp[1]==0:
                        heapq.heappop(buy)
                if m: heapq.heappush(sell,[p,m])
        ans=sum([t[1] for t in buy+sell])
        return ans % (10**9+7)

#最小堆

三、有界数组中指定下标处的最大值

给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标从 0 开始计数）：

nums.length == n
nums[i] 是 正整数 ，其中 0 <= i < n
abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1
nums 中所有元素之和不超过 maxSum
nums[index] 的值被最大化

返回你所构造的数组中的 nums[index] 。

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        l=index
        r=n-1-index
        
        def compu(x,l):
            if l>=x-1:
                return x*(x-1)//2+l-x+1
            else:
                return (2*x-l-1)*l//2
            
        lp,rp=1,maxSum
        while lp<=rp:
            mid=(lp+rp)//2
            #print(lp,rp,compu(mid,l),compu(mid,r),mid)
            if compu(mid,l)+compu(mid,r)+mid>maxSum:
                rp=mid-1
            else:
                lp=mid+1
        return min(lp,rp)

#经典二分（对答案）