주어진 배열로 만들 수있는 주어진 크기의 유사한 그룹의 최대 수

Question

나는 반드시 고유하고 그룹의 크기가 아니라 숫자의 배열을 부여받습니다. 배열을 $ b $ 으로 표시하고 그룹의 크기가 $ a $ 입니다.

$ a $ 의 $ b $ . 원소가 그룹에서 사용되면 소모됩니다. 그룹은 $ B $ 에서 요소가 계속 사용할 수있는 한 동일한 값을 가진 하나 이상의 요소를 가질 수 있습니다.

예 :

1. 입력 배열이 $ \ {1, 2, 3, 1, 2, 3, 4 \} $ 및 그룹 크기가 $ 3 $ 만들 수있는 최대 그룹 수는 $ 2 $ 입니다. "> $ \ {1, 2, 3 \} $ 및 $ \ {1, 2, 3 \} $
2. 입력 배열이 $ \ {1, 3, 3, 3, 6, 3, 10 \} $ 및 그룹 크기가 $ 4 $ 만들 수있는 최대 그룹 수는 $ 1 $ 입니다. 이는 $ \ {1, 3, 3, 3 \} $ .

내가 지금까지 시도한 것은 방정식을 틀지 만, 그 후에, 나는 그들을 해결하기 위해 알고리즘을 생각하는 것에 어려움을 겪고있다.

$ F_1 $ 요소 $ b_1 $ , $ F_2 $ 요소 $ b_2 $ 등을 $ b_n $ , $ b_1 \ dots b_n $ 은 배열 $ b $ .

이제 $ n_1, n_2, \ dots n_i $ 을 선택해야합니다

1. $ N_1 + N_2 + \ DOTS + N_I= A $
2. $ K \ CDOT N_1 \ LEQ F_1 \ TEXT {,} K \ CDOT N_2 \ LEQ F_2 \ TEXT {,} \ DOTS \ TEXT {,} K \ CDOT N_I \ LEQ F_I $
3. $ k $ 은 그룹의 수가 많고 그것을 최대화해야합니다.
$ B $ 의 길이는 $ 10 ^ 5 $ 및 $ a $ 은 $ 10 ^ 5 $

문제에 대한 탐욕 스럽거나 역동적 인 접근 방식을 찾도록 도와주세요.

Answer 1

함수 $$ F : \ MATHBB {n} \ Nightwarl \ {0, 1 \} : f (k)= \ 시작 {사례} 1; & \ text {크기의 솔루션이있는 경우 $ k $,} \\ 0; & \ text {그렇지 않으면} \ end {사례} $$ $ k $ 의 솔루션이 없다면 $ k + 1 $의 솔루션이 없기 때문에 Monoton입니다. . 즉, $ k $ 의 가치를 바이너리 검색 할 수 있습니다 "> $ [1, | b |] $ $ k $ 의 솔루션이있는 가장 큰 $ k $ 을 출력하십시오. 따라서 우리는 $ o (\ log | b |) $ 팩터의 결정 문제로 문제를 해결합니다.

$ k $ 의 고정 값의 경우 욕심 많은 솔루션이 충분합니다. 일부 요소 $ b_i $ 의 $ f_i $ 사본을 가지고 있다면 각 세트는 대부분의 < SPAN 클래스="수학 용기"> $ \ left \ lfloor \ frac {f_i} {k} \ \ rfloor $ . 그래서 우리는 $ k $ 만있는 경우에만 크기의 솔루션을 가지고 있습니다. $$ \ sum \ limits_ {i= 1} ^ {n} \ left \ lfloor \ frac {f_i} {k} \ right \ rfloor \ geq a. $$

운동으로서 욕심 많은 솔루션이 최적임을 증명하십시오. 실행 시간은 $ o (| b | \ log | b |)로 바인딩 될 수 있습니다. $