Aggressive cows – Omówienie zadania z Amerykańskiej Olimpiady Informatycznej USACO – poziom Gold

Aggressive cows – Omówienie zadania z Amerykańskiej Olimpiady Informatycznej USACO – poziom Gold

Szczegółowe omówienie zadania Aggressive cows:

Link do powyższego omówienia zadania Aggressive cows:
https://youtu.be/YWhVqyMjtjE?t=2286

Link do treści zadania Aggressive cows:
https://www.spoj.com/problems/AGGRCOW/

——
Zadanie Aggressive cows jest szkoleniowym zadaniem pokazującym algorytm Binary Search po wyniku:
https://youtu.be/YWhVqyMjtjE?t=3623

—–
Zadanie Aggressive cows pochodzi z dywizji GOLD Amerykańskiej Olimpiady Informatycznej USACO – odpowiednika naszej Olimpiady Informatycznej Licealistów
Daje piękny wpis do CV:
https://youtu.be/P2sLFZBjOmM?t=7223

Dlaczego warto brać udział w Amerykańskiej Olimpiady Informatycznej USACO?
https://youtu.be/K7fZfJ8nN6A?t=6848


Zadanie omawia Tomek Kwiatkowski:
https://youtu.be/xZCGtGh2he0?t=5584

——–
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
——-

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

const int MAXN = 100*1000 + 7;

int pozycje[MAXN]; // pozycje stodół

int ile_stodol, ile_krow;

bool czy_min_odl(int d)
{
	int ost = -1000*1000*1000, ile_miejsc_ok = 0;
	for(int i = 0; i < ile_stodol; i++)
	{
		if(pozycje[i] - ost >= d)
		{
			ile_miejsc_ok++;
			ost = pozycje[i];
		}
	}
	if(ile_miejsc_ok >= ile_krow)
		return true;
	return false;
}

int binsearch()
{
	int pocz = 1, kon = 1000*1000*1000;
	while(pocz < kon)
	{
		int sr = (pocz + kon + 1)/2;
		if(czy_min_odl(sr))
			pocz = sr;
		else
			kon = sr - 1;
	}
	return pocz;
}

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

	int t;
	cin >> t;
	while(t--)
	{
		cin >> ile_stodol >> ile_krow;
		for(int i = 0; i < ile_stodol; i++)
			cin >> pozycje[i];
		sort(pozycje, pozycje + ile_stodol);
		cout << binsearch() << '\n';
	}
	return 0;
}
Kod C++ programu Aggressive cows, który jest omówiony w powyższym filmie i który otrzymuje 100%

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz