Parallel ikkilik qidiruv
Parallel ikkilik qidiruv
Misol masala
Sizga ta odam va ta yer berilgan. Har bir yer () ning egasi (), va har bir odamning maqsad resurs darajasi bor.
Parallel ikkilik qidiruv
Sizga ta odam va ta yer berilgan. Har bir yer () ning egasi (), va har bir odamning maqsad resurs darajasi bor.
ta hodisa ketma-ket sodir bo‘ladi. Har bir hodisa uchligi bilan beriladi va dan gacha bo‘lgan yerlar resurs ishlab chiqarishini anglatadi.
E’tibor bering, yerlar doira shaklida joylashganligi sababli dan katta bo‘lishi mumkin.
Agar biror odam kesmada ta yerga ega bo‘lsa, u holda u resurs oladi.
Har bir odam uchun, ular qaysi hodisadan keyin o‘z maqsad resurs darajasiga yetishini aniqlashingiz kerak. Agar bu imkonsiz bo‘lsa, -1 chiqaring.
Har bir odam uchun masalani alohida yechib, javob bo‘yicha ikkilik qidiruvdan foydalanishingiz mumkin.
can(x, m) = true agar odam birinchi ta hodisadan keyin kerakli miqdordagi resursni to‘play olsa.
can(x, m) ga javob berish uchun, birinchi ta hodisani tez qo‘shish va o‘sha odamning yerlaridagi hissani hisoblash kerak. Buni Fenwick daraxti yoki segment daraxti yordamida qilish mumkin.
Bitta odam uchun g‘oya:
Bu yerda muammo shundaki, biz bir xil hodisalarni ko‘p marta qo‘shamiz va olib tashlaymiz.
Asosiy g‘oya: ikkilik qidiruvga javobni barcha odamlar uchun bir vaqtning o‘zida topish.
can(x, m) funksiyasining o‘zi yetarlicha tez ishlaydi, sekin bo‘layotgani esa hodisalarni qayta-qayta qo‘shish/olib tashlashdir.
Shuning uchun, odamlarni o‘rtadagi qiymat bo‘yicha javobiga qarab bo‘lib, guruhlarni rekursiv qayta ishlaymiz.
Shu tarzda takroriy yangilanishlar sonini kamaytiramiz va yaxshi asimptotikaga erishamiz.
Xuddi shu g‘oyani iterativ tarzda ham yozish mumkin.
Har bir odam uchun ikkilik qidiruv chegaralarini saqlaymiz:
tl[x] — chap chegaratr[x] — o‘ng chegaraBoshlang‘ich holatda hammasi uchun:
tl[x] = 0tr[x] = K + 1Har bir iteratsiyada odamlarni ularning o‘rta nuqtasi (tl[x] + tr[x]) / 2 bo‘yicha guruhlaymiz, hodisalarni ketma-ket qo‘shamiz va can(x, m) ni tekshiramiz.
int solve(int x) {
int l = 0, r = K + 1;
while (l < r) {
int m = (l + r) / 2;
add_updates(1, m);
if (can(x, m)) {
r = m;
} else {
l = m + 1;
}
remove_updates(1, m);
}
if (l == K + 1) return -1;
return l;
}
void solve(int l, int r, vector<int> can_x) {
if (can_x.empty()) {
return;
} else if (l == r) {
for (int x: can_x) {
if (l == K + 1) {
res[x] = -1;
} else {
res[x] = l;
}
}
return;
}
int m = (l + r) / 2;
add_updates(l, m);
vector<int> can_l, can_r;
for (int x: can_x) {
if (can(x, m)) {
can_l.push_back(x);
} else {
can_r.push_back(x);
}
}
remove_updates(l, m);
solve(l, m, can_l);
solve(m + 1, r, can_r);
}
void solve() {
for (int i = 1; i <= n; i++) {
tl[i] = 0;
tr[i] = K + 1;
}
for (int it = 0; it < LOG_K; it++) {
for (int i = 0; i <= K; i++) {
query[i].clear();
}
for (int i = 1; i <= n; i++) {
query[(tl[i] + tr[i]) / 2].push_back(i);
}
for (int m = 0; m <= K; m++) {
if (m > 0) {
add_updates(m, m);
}
for (int x : query[m]) {
if (can(x, m)) {
tr[x] = m;
} else {
tl[x] = m + 1;
}
}
}
remove_updates(1, K);
}
}