찾다
백엔드 개발PHP 튜토리얼모든 매장에 유통되는 제품의 최대 최소화

Minimized Maximum of Products Distributed to Any Store

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

힌트:

  1. x가 어떤 숫자보다 작으면 배포할 방법이 없고, x가 해당 숫자보다 작지 않으면 항상 배포할 방법이 있다는 단조로운 특성이 있습니다.
  2. 어떤 매장에 납품하는 상품의 개수가 k를 넘지 않는 숫자 k가 주어진다면, 모든 상품이 유통될 수 있는지 판단할 수 있나요?
  3. 모든 매장에 k개 이상의 제품을 제공하지 않도록 모든 제품을 배포할 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환하는 canDistribute(k) 함수를 구현하세요. 이 기능을 사용하여 가능한 가장 작은 k에 대한 이진 검색을 수행하세요.

해결책:

매장에 할당된 최대 제품 수(x)에 대해 이진 검색을 사용할 수 있습니다. 다음은 단계별 설명과 PHP 솔루션입니다.

접근하다

  1. 이진 검색 설정:

    • 하한(왼쪽)을 1로 설정합니다(각 매장은 최소 1개의 제품을 구입할 수 있으므로).
    • 상한(오른쪽)을 수량 배열의 최대 수량으로 설정합니다(최악의 경우 한 매장에서 해당 유형의 모든 제품을 가져옵니다).
    • 우리의 목표는 x 값(모든 매장에 제공되는 최대 제품)을 최소화하는 것입니다.
  2. 이진 검색 논리:

    • 각 중간 지점 x에 대해 어떤 매장도 x개 이상의 제품을 보유하지 않도록 모든 제품을 배포하는 것이 가능한지 확인하세요.
    • 타당성을 판단하려면 도우미 함수 canDistribute(x)를 사용하세요.
  3. 타당성 검사(canDistribute):

    • 각 제품 유형 수량에 대해 매장당 x개 제품을 초과하지 않고 해당 제품 유형을 배포하는 데 필요한 최소 매장 수를 계산하세요.
    • 모든 제품 유형에 필요한 매장을 합산하세요.
    • 필요한 총 매장 수가 n 이하인 경우 매장당 최대 로드 x를 사용하여 배포가 가능합니다. 그렇지 않으면 불가능합니다.
  4. 이진 검색 조정:

    • canDistribute(x)가 true를 반환하면 x가 실행 가능한 솔루션이라는 의미이지만 x를 최소화하고 싶으므로 올바른 경계를 조정하세요.
    • false를 반환하는 경우 x가 너무 작으므로 왼쪽 경계를 늘립니다.
  5. 결과:

    • 이진 검색이 완료되면 왼쪽에 가능한 최소 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
?>

설명:

  1. canDistribute 함수:

    • 각 수량에 대해 수량을 x로 나누어 필요한 최소 매장 수를 계산합니다(각 매장에서 전체 제품 수를 얻을 수 있으므로 ceil을 사용하여 반올림).
    • 누적 필수 매장 수가 n개를 초과하면 false를 반환합니다.
  2. x에 대한 이진 검색:

    • 이진 검색은 실행 가능한 최소 값에 수렴할 때까지 x의 범위를 반복적으로 줄입니다.
  3. 효율성:

    • 이 솔루션은 주어진 제약 조건 내에서 실현 가능한 O(log(max_Quantity) * m)에서 이진 검색이 실행되므로 큰 입력 크기(n 및 m 최대 10^5)에 효율적입니다.

이 접근 방식은 x를 최소화하여 제품이 매장 전체에 최대한 균등하게 배포되도록 합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

  • 링크드인
  • 깃허브

위 내용은 모든 매장에 유통되는 제품의 최대 최소화의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
Laravel의 플래시 세션 데이터로 작업합니다Laravel의 플래시 세션 데이터로 작업합니다Mar 12, 2025 pm 05:08 PM

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

PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법Mar 14, 2025 am 11:42 AM

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

Laravel 테스트에서 단순화 된 HTTP 응답 조롱Laravel 테스트에서 단순화 된 HTTP 응답 조롱Mar 12, 2025 pm 05:09 PM

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

Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트Mar 13, 2025 pm 12:08 PM

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

Storage :: 다운로드로 Laravel에서 파일 다운로드를 발견하십시오Storage :: 다운로드로 Laravel에서 파일 다운로드를 발견하십시오Mar 06, 2025 am 02:22 AM

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

PHP에서 늦은 정적 결합의 개념을 설명하십시오.PHP에서 늦은 정적 결합의 개념을 설명하십시오.Mar 21, 2025 pm 01:33 PM

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

PHP 로깅 : PHP 로그 분석을위한 모범 사례PHP 로깅 : PHP 로그 분석을위한 모범 사례Mar 10, 2025 pm 02:32 PM

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

Laravel 서비스 제공 업체를 등록하고 사용하는 방법Laravel 서비스 제공 업체를 등록하고 사용하는 방법Mar 07, 2025 am 01:18 AM

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

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

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

뜨거운 도구

mPDF

mPDF

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

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

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

SublimeText3 Linux 새 버전

SublimeText3 Linux 새 버전

SublimeText3 Linux 최신 버전

SublimeText3 영어 버전

SublimeText3 영어 버전

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