Zakup działki – Omówienie zadania – Binary Search

Zakup działki – Omówienie zadania – Binary Search

Szczegółowe omówienie zadania Zakup działki:

Link do powyższego omówienia zadania Zakup działki: https://youtu.be/OJtDgY3dPlY?t=1198
Omówienie kodu zadania Zakup działki: https://youtu.be/OJtDgY3dPlY?t=4448

Link do treści zadania Zakup działki: https://szkopul.edu.pl/problemset/problem/zak/site/

Zadanie Zakup działki to szkoleniowe zadanie pokazujące algorytm Binary Search (wyszukiwanie połówkowe): https://youtu.be/OJtDgY3dPlY?t=2247
Złożoność Binary search: https://youtu.be/OJtDgY3dPlY?t=3791
Kod algorytmu Binary Search: https://youtu.be/OJtDgY3dPlY?t=4466
Binary Search i encyklopedia: https://youtu.be/OJtDgY3dPlY?t=5309
Binary Search jest prosty i szybki! https://youtu.be/OJtDgY3dPlY?t=6005

Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/
Zajęcia: : https://oki.org.pl/harmonogram-zajec/

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109


Kod C++ programu "Zakup działki", który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200*1000 + 7;

// pozycje dzialek
int pozycjeDzialek[MAXN];

// wyszukaj w tablicy pozycjeDzialek indeksu najblizszego
// elementu wiekszego badz rownego wartoscSzukana
int BinarySearch(int lewo, int prawo, int wartoscSzukana)
{
	while (lewo < prawo) {
		int srodek = (lewo + prawo) / 2;
		if (pozycjeDzialek[srodek] >= wartoscSzukana)
			prawo = srodek; // wynik jest w przedziale [lewo, srodek]
		else
			lewo = srodek + 1; // wynik jest w przedziale [srodek + 1, prawo]
	}

	return lewo;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int liczbaDzialek, liczbaZapytan;
	cin >> liczbaDzialek >> liczbaZapytan;
	for (int i = 1; i <= liczbaDzialek; ++i) {
		int x;
		cin >> x;
		pozycjeDzialek[i] = x;
	}

	pozycjeDzialek[0] = -(1000*1000*1000 + 7);
	pozycjeDzialek[liczbaDzialek + 1] = 2000*1000*1000 + 7;
	for (int i = 1; i <= liczbaZapytan; ++i) {
		int a;
		cin >> a;

		// znajdz indeks najblizszej na prawo dzialki
		int ind = BinarySearch(1, liczbaDzialek + 1, a);

		// sprawdz pozycje dzialki na prawo oraz na lewo od nas
		int	prawaDzialka = pozycjeDzialek[ind];
		int lewaDzialka = pozycjeDzialek[ind - 1];

		// wez te, do ktorej mamy mniejsza odleglosc
		int wynik = min(abs(prawaDzialka - a), abs(lewaDzialka - a));
		cout << wynik << '\n';
	}

	return 0;
}
Kod C++ programu "Zakup działki", który jest omówiony w powyższym filmie i który otrzymuje 100%

 


Kod Python programu Zakup działki, który otrzymuje 100%:

# wyszukaj w tablicy positions indeksu najblizszego
# elementu wiekszego badz rownego val
def BS(lo, hi, val):
	while (lo < hi): mid = (lo + hi) // 2 if (positions[mid] >= val):
			hi = mid
		else:
			lo = mid + 1

	return lo

# liczba dzialek, liczba zapytan
n, q = map(int, input().split())

# pozycje dzialek
positions = list(map(int, input().split()))
positions.insert(0, -(1e9 + 7))
positions.append(2e9 + 7)

for i in range(q):
	a = int(input())

	# znajdz indeks najblizszej na prawo dzialki
	ind = BS(1, n+1, a)

	# sprawdz pozycje dzialki na prawo oraz na lewo od nas
	rightField = positions[ind]
	leftField = positions[ind - 1]

	# wez te, do ktorej mamy mniejsza odleglosc
	ans = min(abs(rightField - a), abs(leftField - a))
	print(ans)

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz