[14510] 나무 높이

나무에 물을 주는데

홀수번째 날은 1만큼 크고

짝수번째 날은 2만큼 큰다

 

모든 나무가 나무들의 최댓값만큼 자라야 한다

 

나무가 더 자라야할 길이에서 2를 나눈 몫과 나머지를 구해서

2만큼 자라야 할 부분이랑 

1만큼 자라야 할 부분으로 나눠서 계산했다

 

일단 짝수번째 날은 2만큼 자라야 할 부분만 신경쓰면 된다

 

홀수번째 날에는 1만큼 자라야 할 부분을 먼저 신경써야 한다

2만큼 자랄땐 딱 1이 필요한 경우를 해결하지 못하기 때문이다

 

다만 1만큼 자라야 할 부분 다 쓰고 2만큼 자라야할 부분이 잔뜩 남아있으면

1만큼 자랄때 2만큼 자랄 부분을 쪼개서 1만큼 두번 자라는걸로 생각할 수 있다

 

다만 이 작업은 홀수번째 날을 놀게 될 때 쓰는거지 

기본적으로 2만큼 한번 자랄걸 1만큼 두번 자라는 것이므로

두배의 시간이 든다

 

따라서 남은 작업이 두번 자라는 경우가 많아서 한번 자라는 경우에 하나 나눠주어도 무관할때만 나눠준다

 

T = int(input())
for test_case in range(1, T + 1):
    N = int(input().strip())
    trees = list(map(int, input().split()))

    max_tree = max(trees)
    twos = 0
    ones = 0
    for tree in trees:
        twos += (max_tree - tree) // 2
        ones += (max_tree - tree) % 2

    # print(f"{twos}, {ones}")

    day = 0
    while True:
        if ones == 0 and twos == 0:
            break
        day += 1
        if day%2 == 1:
            if ones:
                ones -= 1
            else:
                if ones+1 <= twos-1:
                    twos -= 1
                    ones += 1
        else:
            if twos:
                twos -= 1

    print(f"#{test_case} {day}")
    # print("")