【周赛+双周赛20220904】T4

分析

子数组sum好处理，max怎么办
segTree慢，用sortedlist模拟即可

ac code

from sortedcontainers import SortedList


class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        # 子数组max值记录的方法：使用SortedList
        n = len(chargeTimes)
        stl = SortedList()
        
        preSum = list(accumulate(runningCosts, initial = 0))
        
        l = 0
        tmpSum = 0
        tmpMax = 0
        ans = 0
        for r in range(n):
            stl.add(chargeTimes[r])
            tmpMax = stl[-1]
            k = r - l + 1
            tmpSum = tmpMax + k * (preSum[r + 1] - preSum[l])
            if tmpSum <= budget:
                ans = max(ans, k)
            else:
                while l <= r and tmpSum > budget:
                    stl.discard(chargeTimes[l])
                    l += 1
                    if len(stl) == 0:
                        break
                    tmpMax = stl[-1]
                    k = r - l + 1
                    tmpSum = tmpMax + k * (preSum[r + 1] - preSum[l])
        
        return ans
        
        

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

分析

两个优先队列存
一个存（结束时间，房间号）
另一个存目前可用的会议室

ac code

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        m = len(meetings)
        meetings.sort()
        d = defaultdict(int) # 记录多少次
        pq1 = [] # (结束时间, 第几个房间)
        heapify(pq1)
        pq2 = list(range(n))
        heapify(pq2)
        
        cur = 0
        
        for i in range(m):
            # preprocedure
            while len(pq1) > 0:
                endTime, idx = heappop(pq1)
                if endTime <= meetings[i][0]:
                    heappush(pq2, idx)
                else:
                    heappush(pq1, (endTime, idx))
                    break
                
                
            if len(pq2) > 0:
                idx = heappop(pq2)
                #print(idx)
                d[idx] += 1
                #print((meetings[i][1], idx))
                heappush(pq1, (meetings[i][1], idx))
            else:
                endTime, idx = heappop(pq1)
                #print(idx)
                d[idx] += 1
                heappush(pq1, (max(endTime + meetings[i][1] - meetings[i][0], meetings[i][1]), idx))
                
                
        #print(d)
        ans = inf
        maxn = max(d.values())
        for k in d:
            if d[k] == maxn:
                ans = min(ans, k)
        
        return ans
            
            
        
        

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49