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 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
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;
}