counts[i]가 유형 i의 항목 수를 나타내는 counts라는 숫자 목록이 있다고 가정합니다. 또 다른 값 k가 있습니다. 각 그룹에는 고유한 유형의 항목이 있어야 하므로 찾을 수 있는 크기가 k인 그룹의 최대 수를 찾아야 합니다.
따라서 입력이 counts =[2, 3, 5, 3] k =2와 같으면 4가지 유형의 항목이 각각 a, b, c, d로 표시되기 때문에 출력은 6이 됩니다. k =2의 다음 그룹을 가질 수 있습니다. 여기서 모든 요소는 고유한 유형입니다:[(c, a), (b, a), (c, b), (c, b), (d, a), (d, a)].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- possible() 함수를 정의하십시오. 여기에는 카운트, 그룹, k가 필요합니다.
- 필수 :=그룹 * k
- 0에서 카운트 크기 사이의 i에 대해
- temp :=최소 개수[i], 그룹 및 필수
- 필수 :=필수 - 임시
- 필요한 경우 0과 같으면
- 참 반환
- 거짓을 반환
- solve() 함수를 정의합니다. 계산이 필요합니다. k
- res :=0
- l :=0
- r :=개수에 있는 모든 요소의 합계
- l <=r인 동안, do
- m :=l + (r - l) / 2의 바닥
- 만약 가능한(counts, m, k)가 참이면
- l :=m + 1
- res :=res 및 m의 최대값
- 그렇지 않으면
- r :=m - 1
- 반환 결과
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def possible(counts, groups, k): required = groups * k for i in range(len(counts)): temp = min(counts[i], groups, required) required -= temp if required == 0: return True return False def solve(counts, k): res = 0 l = 0 r = sum(counts) while l <= r: m = l + (r - l) // 2 if possible(counts, m, k): l = m + 1 res = max(res, m) else: r = m - 1 return res counts = [2, 3, 5, 3] k = 2 print(solve(counts, k))
입력
[2, 3, 5, 3], 2
출력
6