Хариуг өөрийг нь Binary Search ашиглан хайдаг арга: «энэ хариу болох уу?» гэдгийг л шалгана.

IntermediateХугацаа: O(n log S), S — нийлбэрСанах ой: O(n)
HackerRank дээр бодох

Эхлээд жижиг бодлого

a = [7, 2, 5, 10, 8] хуудастай 5 номыг дарааллаар нь 2 сурагчид хуваана. Хамгийн их уншсан сурагч хамгийн цөөндөө хэдэн хуудас унших вэ?

7 + 2 + 5 = 14 ба 10 + 8 = 18 гэж хуваавал хамгийн их нь 18. Үүнээс сайн хуваалт байхгүй. Хариу: 18.

Энгийн аргаас санаа руу

Энгийн арга: бүх хуваалтыг шалгана. n = 100 000 ном, k = 50 сурагч бол хуваалтын тоо тоолж баршгүй их.

Харин эсрэгээр нь асууя: "Нэг сурагч x хуудаснаас ихгүй уншвал k сурагч хүрэлцэх үү?" Үүнийг нэг гүйлтээр шалгана: номыг дараалан өгч, x давах гэвэл дараагийн сурагч руу шилжинэ. x өсөх тусам хариу "болохгүй"-гээс "болно" руу ганц удаа л солигдоно. Тэр хилийг Binary Search ашиглан олно.

Нэр томьёо ба тэмдэглэгээ

lo, hi
Хариу байж болох хүрээ. lo нь хамгийн зузаан ном, hi нь бүх номын нийлбэр.
mid
Шалгаж буй хариу: (lo + hi) / 2.
parts(x)
Нэг сурагч x хуудаснаас ихгүй уншвал хэдэн сурагч хэрэгтэйг Greedy аргаар тоолдог function.
монотон
x өсөхөд parts(x) хэзээ ч өсөхгүй. Тиймээс "болно" гэсэн хариунууд нэг талдаа цугларна.
a
7
0
2
1
5
2
10
3
8
4
k = 2lo = 10hi = 32
шалгасан mid
хоосон

5 номыг дарааллаар нь 2 сурагчид хуваана. Хамгийн их уншсан сурагчийн хуудас аль болох цөөн байх ёстой. Хариу 10-аас 32 хүртэл байна: 10 бол хамгийн зузаан ном, 32 бол бүх номын нийлбэр.

Алхам 1 / 14
Хурд
  • Нэг сурагчийн ном
  • Дараагийн сурагчийн ном
  • Эцсийн хуваалт
Слайд 1 / 6

Номоо хуваая

5 номыг дарааллаар нь 2 сурагчид хуваана. Хамгийн их уншсан сурагч аль болох цөөн хуудас уншаасай. Бүх хуваалтыг шалгавал удаан.

binary-search-answer.cpp
#include <bits/stdc++.h>
using namespace std;
int n, k, a[100005];
int parts(long long x) {
int c = 1;
long long s = 0;
for (int i = 0; i < n; i++) {
if (s + a[i] > x) {
c++;
s = 0;
}
s += a[i];
}
return c;
}
int main() {
cin >> n >> k;
long long lo = 0, hi = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
lo = max(lo, (long long)a[i]);
hi += a[i];
}
while (lo < hi) {
long long mid = (lo + hi) / 2;
int c = parts(mid);
if (c <= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
cout << lo << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

«Хамгийн их нь хамгийн бага байх», «хамгийн бага хугацаа» гэх мэт бодлогод хариуг шууд олох хэцүү. Харин өгсөн хариу болох эсэхийг шалгах амархан байдаг.

Яаж ажилладаг вэ?

Жишээ: n номыг дарааллаар нь k сурагчид хуваана. Хамгийн их уншсан сурагчийн хуудсыг аль болох цөөн болгоно. 1. Хариу lo = хамгийн зузаан ном, hi = бүх номын нийлбэр хоёрын хооронд байна. 2. mid = (lo + hi) / 2 гэж олно. Нэг сурагч mid хуудаснаас ихгүй уншвал хэдэн сурагч хэрэгтэйг Greedy аргаар тоолно. 3. Сурагчийн тоо k-гаас хэтрэхгүй бол болж байна: hi = mid. Үгүй бол lo = mid + 1. 4. lo = hi болоход тэр л хариу. Оролт: n, k, дараа нь n тоо.

Яагаад зөв, хэр хурдан бэ?

x хуудас болж байвал түүнээс их ямар ч хуудас мөн болно: өмнөх хуваалтаа хэвээр ашиглаж болно. Тиймээс "болно" хариунууд хүрээний баруун талд цугларна. hi = mid нь "болно"-г хадгалж, lo = mid + 1 нь "болохгүй"-г хаяна. lo = hi болоход тэр нь хамгийн бага "болно".

Шалгалт бүр O(n). Хүрээ алхам бүрт хоёр дахин багасна. a[i] ≤ 10⁹, n = 10⁵ бол hi ≈ 10¹⁴ тул 47 орчим шалгалт: нийт 5 сая орчим алхам.

Түгээмэл алдаа

  • lo-г 0-ээс эхлүүлэх. Хамгийн зузаан номоос бага x дээр тэр ном хэнд ч багтахгүй тул parts утгагүй тоо буцаана. lo нь хамгийн зузаан ном байх ёстой.
  • Нийлбэр int-д багтахгүй. lo, hi, s-ийг long long болго.
  • hi = mid - 1 гэж бичих. mid өөрөө хариу байж болох тул hi = mid.
  • while (lo <= hi) гэж бичвэл hi = mid үед loop дуусахгүй. Энэ хэлбэрт lo < hi хэрэгтэй.

Хязгаарын тохиолдол

  • k = 1: ганц сурагч бүгдийг уншина, хариу бүх номын нийлбэр. Жишээ дээр 32.
  • k = n: ном бүрт нэг сурагч, хариу хамгийн зузаан ном. Жишээ дээр 10.
  • Нэг маш зузаан ном: хариу хэзээ ч түүнээс бага болохгүй, lo тэндээс эхэлнэ.

Өөрийгөө шалга

  1. a = [7, 2, 5, 10, 8] үед parts(17) хэд вэ?

    Хариу харах

    3: 7 + 2 + 5 = 14, 10, 8. 10 + 8 = 18 нь 17-гоос их.

  2. Яагаад hi = mid гэж бичээд mid - 1 гэж бичдэггүй вэ?

    Хариу харах

    mid болж байгаа тул өөрөө хариу байж болно. Хасвал хариугаа алдана.

  3. Ижил номыг 3 сурагчид хуваавал хариу хэд вэ?

    Хариу харах

    14: 7 + 2 + 5 | 10 | 8.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.a = [1, 2, 3, 4, 5], k = 2 үед lo, hi, mid ямар утга авахыг алхам алхмаар бич.

    Hint харах

    lo = 5, hi = 15-аас эхэл.

    Хариу ба тайлбар

    mid = 10 болно (hi = 10), mid = 7 болохгүй (lo = 8), mid = 9 болно (hi = 9), mid = 8 болохгүй (lo = 9). Хариу 9: 1 + 2 + 3 | 4 + 5.

  2. 2.Хариунаас гадна хуваалтыг өөрийг нь хэвлэ.

    Hint харах

    Хариу олдсоны дараа parts доторх Greedy-г дахин ажиллуул.

    Хариу ба тайлбар

    lo олдсоны дараа номыг дахин дараалан өгч, s + a[i] > lo болох бүрт шинэ сурагч эхлүүлэн хэвлэнэ. Сурагч k-гаас цөөн гарч болно. Хоосон сурагч зөвшөөрөгдөхгүй бол олон номтой сурагчаас нэг ном салгаж өгнө.

  3. 3.n машин байна, i-р машин нэг бүтээгдэхүүнийг t[i] секундэд хийдэг. Бүгд зэрэг ажиллавал хамгийн багадаа хэдэн секундэд m бүтээгдэхүүн хийх вэ?

    Hint харах

    T секундэд нийт хэдэн бүтээгдэхүүн хийх вэ? T өсөхөд энэ тоо ч өснө.

    Хариу ба тайлбар

    T секундэд T / t[0] + T / t[1] + … бүтээгдэхүүн хийнэ. Үүнийг m-тэй харьцуулж, T дээр Binary Search хийнэ. lo = 1, hi нь хамгийн хурдан машин ганцаараа m бүтээгдэхүүн хийх хугацаа.

Жишээ

Оролт

5 2
7 2 5 10 8

Гаралт

18

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.