import heapq
from typing import List, Optional, Dict


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Que:
    def __init__(self, idx, num):
        self.idx = idx
        self.num = num

    def __lt__(self, other):
        if self.num < other.num:
            return True
        elif self.num == other.num:
            return self.idx <= other.idx
        return False

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        for i in range(len(nums)):
            m = target - nums[i]
            if m in num_map:
                return [num_map[m], i]
            else:
                num_map[nums[i]] = i
        return []

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        r = None
        res = None
        add = 0
        while l1 and l2:
            sum = l1.val + l2.val + add
            if r:
                r.next = ListNode(sum % 10)
                r = r.next
            else:
                r = ListNode(sum % 10)
                res = r
            add = int(sum / 10)
            l1 = l1.next
            l2 = l2.next
        if l1:
            l = l1
        else:
            l = l2
        while l:
            sum = l.val + add
            if r:
                r.next = ListNode(sum % 10)
                r = r.next
            else:
                r = ListNode(sum % 10)
                res = r
            add = int(sum / 10)
            l = l.next
        if add:
            r.next = ListNode(add)
        return res

    def lengthOfLongestSubstring(self, s: str) -> int:
        res = 0
        start = 0
        ch_set = dict()
        for i, ch in enumerate(s):
            while ch in ch_set:
                idx = ch_set.pop(ch)
                if idx >= start:
                    res = max(res, i - start)
                    start = idx + 1
                    break
            ch_set[ch] = i
        res = max(res, len(s) - start)
        return res

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums = []
        if nums1:
            nums.extend(nums1)
        if nums2:
            nums.extend(nums2)
        nums.sort()
        if len(nums) % 2 == 0:
            mid = int(len(nums) / 2)
            return (nums[mid] + nums[mid - 1]) / 2
        return nums[int(len(nums) / 2)]

    def longestPalindrome(self, s: str) -> str:
        l = len(s)
        if l < 2:
            return s
        m: List[List[int]] = []
        ml = 1
        begin = 0
        for i in range(l):
            m.append([])
            for j in range(l):
                if i == j:
                    m[i].append(1)
                else:
                    m[i].append(0)

        for i in range(2, l + 1):
            for j in range(l):
                k = i + j - 1
                if k >= l:
                    break
                if s[j] != s[k]:
                    m[j][k] = 0
                else:
                    if k - j < 3:
                        m[j][k] = 1
                    else:
                        m[j][k] = m[j + 1][k - 1]

                if m[j][k] and k - j + 1 > ml:
                    ml = k - j + 1
                    begin = j
        return s[begin : begin + ml]

    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        res: List[List[str]] = [[] for _ in range(numRows)]
        dirt = 1
        cur = 0
        for i in range(len(s)):
            res[cur].append(s[i])
            cur += dirt
            if cur < 0 or cur >= numRows:
                dirt *= -1
                if cur < 0:
                    cur = 1
                else:
                    cur = numRows - 2
        return ''.join([''.join(i) for i in res])
    def reverse(self, x: int) -> int:
        min_num = -(2 ** 31)
        max_num = (2 ** 31) - 1
        max_i = int(max_num / 10)
        max_mod = max_num % 10
        min_i = int(-min_num / 10)
        min_mod = -min_num % 10
        res = 0
        n = abs(x)
        while n != 0:
            if x > 0 and (res > max_i or (res == max_i and n % 10 > max_mod)):
                return 0
            elif x < 0 and (res > min_i or (res == min_i and n % 10 > min_mod)):
                return 0
            res = res * 10 + n % 10
            n = int(n / 10)
        if x > 0:
            return res
        return -res

    stat_map: Dict[str,List[str]] = {'start': ['start', 'signed', 'number', 'end'],
                'signed': ['end', 'end', 'number', 'end'],
                'number': ['end', 'end', 'number', 'end'],
                'end': ['end', 'end', 'end', 'end']}
    def get_stat(self, stat, ch) -> str:
        if ch == ' ':
            return self.stat_map[stat][0]
        if ch == '+' or ch == '-':
            return self.stat_map[stat][1]
        if ch >= '0' and ch <= '9':
            return self.stat_map[stat][2]
        return 'end'
    def myAtoi(self, s: str) -> int:
        min_num = (2 ** 31)
        max_num = min_num - 1
        l = len(s)
        res = 0
        i = 0
        k = 1
        st = 'start'
        while i < l and st != 'end':
            st = self.get_stat(st, s[i])
            if st == 'signed' and s[i] == '-':
                k = -1
            elif st == 'number':
                res = res * 10 + int(s[i])
                if k > 0 and res > max_num:
                    return max_num
                elif k < 0 and res > min_num:
                    return -min_num
            i = i + 1
        return res * k

    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        r = 0
        n = x
        while n != 0:
            r = r * 10 + n % 10
            n = int(n / 10)
        return r == x

    def get_time(self, cost:List[int], max_length:int, min_length:int, target:int) -> int:
        res = 0
        cost_len = len(cost)
        num: List[int] = [0 for _ in range(cost_len)]
        num = self.make_queue(num, max_length, target)
        while target > 0:
            res += 1
            add_que = True
            que_num = 0
            for i in range(cost_len):
                if num[i] > 0 and res >= cost[i] and res % cost[i] == 0:
                    print(f'{res}: 第{i}条队测完1个人')
                    target -= 1
                    num[i] -= 1
                que_num += num[i]
                if num[i] > min_length:
                    add_que = False
            if add_que and que_num < target:
                num = self.make_queue(num , max_length, target - que_num)
        return res
    def make_queue(self, num:List[int], max_length:int, rest:int) -> List[int]:
        print('-' * 10)
        print(num)
        hq:List[Que] = []
        for i in range(len(num)):
            hq.append(Que(i, num[i]))
        heapq.heapify(hq)
        while rest > 0:
            if hq[0].num >= max_length:
                break
            hq[0].num += 1
            heapq.heapify(hq)
            print(f'第{hq[0].idx}条加1人，总共{hq[0].num}人')
            rest -= 1
        num = [heapq.heappop(hq).num for _ in range(len(hq))]
        print(num)
        print('-' * 10)
        return num
# print(Solution().twoSum([2,7,11,15], 9))
# print(Solution().twoSum([3,2,4], 6))
# print(Solution().twoSum([3,3], 6))
# print(Solution().lengthOfLongestSubstring('abcabcbb'))
# print(Solution().lengthOfLongestSubstring('bbbbb'))
# print(Solution().lengthOfLongestSubstring('pwwkew'))
# print(Solution().lengthOfLongestSubstring(' '))
# print(Solution().lengthOfLongestSubstring(''))
# print(Solution().lengthOfLongestSubstring('dvdf'))
# print(Solution().lengthOfLongestSubstring('abba'))
# print(Solution().findMedianSortedArrays([1,3], [2]))
# print(Solution().findMedianSortedArrays([1,2], [3,4]))
# print(Solution().longestPalindrome('babad'))
# print(Solution().longestPalindrome('cbbd'))
# matrix = [[j + i*3 for i in range(3)] for j in range(3)]
# print(matrix)
# print(Solution().convert('PAYPALISHIRING', 3))
# print(Solution().convert('PAYPALISHIRING', 4))
# print(Solution().convert('A', 1))
# print(Solution().reverse(123))
# print(Solution().reverse(-123))
# print(Solution().reverse(120))
# print(Solution().reverse(6927694924))
# print(Solution().reverse(-7927694924))
# print(Solution().reverse(1563847412))
# print(Solution().myAtoi('42'))
# print(Solution().myAtoi('   -42'))
# print(Solution().myAtoi('4193 with words'))
# print(Solution().isPalindrome(121))
# print(Solution().isPalindrome(-121))
# print(Solution().isPalindrome(10))

print(Solution().get_time([3, 10, 6], 3, 2, 18))