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