2064. 모든 매장에 유통되는 제품의 최대 최소화
난이도:중
주제: 배열, 이진 검색
n개의 전문 소매점이 있음을 나타내는 정수 n이 제공됩니다. 0-인덱스 정수 배열 수량으로 제공되는 다양한 수량의 m개 제품 유형이 있습니다. 여기서 수량[i]은 i번째 제품 유형의 제품 수를 나타냅니다.
다음 규칙에 따라 모든 제품을 소매점에 배포해야 합니다.
- 한 매장에 최대 한 가지 제품 유형만 제공할 수 있지만 수량에는 제한이 없습니다.
- 배포 후 각 매장에는 일정 수(아마도 0)의 제품이 제공됩니다. x는 모든 매장에 제공되는 최대 제품 수를 나타냅니다. x를 가능한 한 작게 만들고 싶습니다. 즉, 모든 매장에 제공되는 최대 제품 수를 최소화하고 싶습니다.
최소 x를 반환합니다.
예 1:
- 입력: n = 6, 수량 = [11,6]
- 출력: 3
-
설명: 최적의 방법 중 하나는 다음과 같습니다.
- 유형 0의 11개 제품은 2, 3, 3, 3의 양으로 처음 4개 매장에 배포됩니다.
- 유형 1의 6개 제품은 다음 금액으로 다른 두 매장에 배포됩니다: 3, 3
- 모든 매장에 제공되는 최대 제품 수는 max(2, 3, 3, 3, 3, 3) = 3입니다.
예 2:
- 입력: n = 7, 수량 = [15,10,10]
- 출력: 5
-
설명: 최적의 방법 중 하나는 다음과 같습니다.
- 유형 0의 15개 제품은 5, 5, 5의 양으로 처음 3개 매장에 배포됩니다.
- 유형 1의 10개 제품은 다음 두 매장에 다음 금액으로 배포됩니다: 5, 5
- 유형 2의 10개 제품은 마지막 2개 매장에 다음 금액으로 배포됩니다: 5, 5
- 모든 매장에 제공되는 최대 제품 수는 최대(5, 5, 5, 5, 5, 5, 5) = 5입니다.
예 3:
- 입력: n = 1, 수량 = [100000]
- 출력: 100000
-
설명: 유일한 최적의 방법은 다음과 같습니다.
- 타입 0의 상품 10만개를 유일한 매장으로 유통합니다.
- 한 매장에 제공할 수 있는 최대 상품 수는 최대(100000) = 100000개입니다.
제약조건:
- m == 수량.길이
- 1 5
- 1 5
힌트:
- x가 어떤 숫자보다 작으면 배포할 방법이 없고, x가 해당 숫자보다 작지 않으면 항상 배포할 방법이 있다는 단조로운 특성이 있습니다.
- 어떤 매장에 납품하는 상품의 개수가 k를 넘지 않는 숫자 k가 주어진다면, 모든 상품이 유통될 수 있는지 판단할 수 있나요?
- 모든 매장에 k개 이상의 제품을 제공하지 않도록 모든 제품을 배포할 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환하는 canDistribute(k) 함수를 구현하세요. 이 기능을 사용하여 가능한 가장 작은 k에 대한 이진 검색을 수행하세요.
해결책:
매장에 할당된 최대 제품 수(x)에 대해 이진 검색을 사용할 수 있습니다. 다음은 단계별 설명과 PHP 솔루션입니다.
접근하다
-
이진 검색 설정:
- 하한(왼쪽)을 1로 설정합니다(각 매장은 최소 1개의 제품을 구입할 수 있으므로).
- 상한(오른쪽)을 수량 배열의 최대 수량으로 설정합니다(최악의 경우 한 매장에서 해당 유형의 모든 제품을 가져옵니다).
- 우리의 목표는 x 값(모든 매장에 제공되는 최대 제품)을 최소화하는 것입니다.
-
이진 검색 논리:
- 각 중간 지점 x에 대해 어떤 매장도 x개 이상의 제품을 보유하지 않도록 모든 제품을 배포하는 것이 가능한지 확인하세요.
- 타당성을 판단하려면 도우미 함수 canDistribute(x)를 사용하세요.
-
타당성 검사(canDistribute):
- 각 제품 유형 수량에 대해 매장당 x개 제품을 초과하지 않고 해당 제품 유형을 배포하는 데 필요한 최소 매장 수를 계산하세요.
- 모든 제품 유형에 필요한 매장을 합산하세요.
- 필요한 총 매장 수가 n 이하인 경우 매장당 최대 로드 x를 사용하여 배포가 가능합니다. 그렇지 않으면 불가능합니다.
-
이진 검색 조정:
- canDistribute(x)가 true를 반환하면 x가 실행 가능한 솔루션이라는 의미이지만 x를 최소화하고 싶으므로 올바른 경계를 조정하세요.
- false를 반환하는 경우 x가 너무 작으므로 왼쪽 경계를 늘립니다.
-
결과:
- 이진 검색이 완료되면 왼쪽에 가능한 최소 x가 유지됩니다.
이 솔루션을 PHP: 2064로 구현해 보겠습니다. 모든 매장에 유통되는 제품의 최대 최소화
<?php /** * @param Integer $n * @param Integer[] $quantities * @return Integer */ function minimizedMaximum($n, $quantities) { ... ... ... /** * go to ./solution.php */ } /** * Helper function to check if we can distribute products with maximum `x` per store * * @param $x * @param $quantities * @param $n * @return bool */ function canDistribute($x, $quantities, $n) { ... ... ... /** * go to ./solution.php */ } // Test cases echo minimizedMaximum(6, [11, 6]); // Output: 3 echo minimizedMaximum(7, [15, 10, 10]); // Output: 5 echo minimizedMaximum(1, [100000]); // Output: 100000 ?>
설명:
-
canDistribute 함수:
- 각 수량에 대해 수량을 x로 나누어 필요한 최소 매장 수를 계산합니다(각 매장에서 전체 제품 수를 얻을 수 있으므로 ceil을 사용하여 반올림).
- 누적 필수 매장 수가 n개를 초과하면 false를 반환합니다.
-
x에 대한 이진 검색:
- 이진 검색은 실행 가능한 최소 값에 수렴할 때까지 x의 범위를 반복적으로 줄입니다.
-
효율성:
- 이 솔루션은 주어진 제약 조건 내에서 실현 가능한 O(log(max_Quantity) * m)에서 이진 검색이 실행되므로 큰 입력 크기(n 및 m 최대 10^5)에 효율적입니다.
이 접근 방식은 x를 최소화하여 제품이 매장 전체에 최대한 균등하게 배포되도록 합니다.
연락처 링크
이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.
- 링크드인
- 깃허브
위 내용은 모든 매장에 유통되는 제품의 최대 최소화의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

Laravel은 직관적 인 플래시 방법을 사용하여 임시 세션 데이터 처리를 단순화합니다. 응용 프로그램에 간단한 메시지, 경고 또는 알림을 표시하는 데 적합합니다. 데이터는 기본적으로 후속 요청에만 지속됩니다. $ 요청-

PHP 클라이언트 URL (CURL) 확장자는 개발자를위한 강력한 도구이며 원격 서버 및 REST API와의 원활한 상호 작용을 가능하게합니다. PHP CURL은 존경받는 다중 프로모토콜 파일 전송 라이브러리 인 Libcurl을 활용하여 효율적인 execu를 용이하게합니다.

Laravel은 간결한 HTTP 응답 시뮬레이션 구문을 제공하여 HTTP 상호 작용 테스트를 단순화합니다. 이 접근법은 테스트 시뮬레이션을보다 직관적으로 만들면서 코드 중복성을 크게 줄입니다. 기본 구현은 다양한 응답 유형 단축키를 제공합니다. Illuminate \ support \ Facades \ http를 사용하십시오. http :: 가짜 ([ 'google.com'=> 'Hello World', 'github.com'=> [ 'foo'=> 'bar'], 'forge.laravel.com'=>

고객의 가장 긴급한 문제에 실시간 인스턴트 솔루션을 제공하고 싶습니까? 라이브 채팅을 통해 고객과 실시간 대화를 나누고 문제를 즉시 해결할 수 있습니다. 그것은 당신이 당신의 관습에 더 빠른 서비스를 제공 할 수 있도록합니다.

Storage :: Laravel Framework의 다운로드 방법은 파일 스토리지의 추상화를 관리하는 동안 파일 다운로드를 안전하게 처리하기위한 간결한 API를 제공합니다. 다음은 예제 컨트롤러에서 Storage :: download ()를 사용하는 예입니다.

기사는 PHP 5.3에 도입 된 PHP의 LSB (Late STATIC BING)에 대해 논의하여 정적 방법의 런타임 해상도가보다 유연한 상속을 요구할 수있게한다. LSB의 실제 응용 프로그램 및 잠재적 성능

PHP 로깅은 웹 애플리케이션을 모니터링하고 디버깅하고 중요한 이벤트, 오류 및 런타임 동작을 캡처하는 데 필수적입니다. 시스템 성능에 대한 귀중한 통찰력을 제공하고 문제를 식별하며 더 빠른 문제 해결을 지원합니다.

Laravel의 서비스 컨테이너 및 서비스 제공 업체는 아키텍처의 기본입니다. 이 기사는 서비스 컨테이너, 세부 정보 서비스 제공 업체 생성, 등록 및 예제와 함께 실질적인 사용을 보여줍니다. 우리는 ove로 시작합니다


핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

mPDF
mPDF는 UTF-8로 인코딩된 HTML에서 PDF 파일을 생성할 수 있는 PHP 라이브러리입니다. 원저자인 Ian Back은 자신의 웹 사이트에서 "즉시" PDF 파일을 출력하고 다양한 언어를 처리하기 위해 mPDF를 작성했습니다. HTML2FPDF와 같은 원본 스크립트보다 유니코드 글꼴을 사용할 때 속도가 느리고 더 큰 파일을 생성하지만 CSS 스타일 등을 지원하고 많은 개선 사항이 있습니다. RTL(아랍어, 히브리어), CJK(중국어, 일본어, 한국어)를 포함한 거의 모든 언어를 지원합니다. 중첩된 블록 수준 요소(예: P, DIV)를 지원합니다.

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

SublimeText3 Linux 새 버전
SublimeText3 Linux 최신 버전

SublimeText3 영어 버전
권장 사항: Win 버전, 코드 프롬프트 지원!
