Zadanie Apple Catching usaco gold

Question

Cześć, zastanawiam się nad rozwiązaniem do zadania : https://usaco.org/index.php?page=viewproblem2&cpid=1233 .

Czytając omówienie nie do końca rozumiem jak rozwiązać ten problem. Może znalazłby się ktoś kto mógłby mi w tym pomóc. https://usaco.guide/problems/usaco-1233-apple-catching/solution

Z góry wielkie dzięki!

Comments

Nie napisałeś, czego konkretnie w tym proponowanym rozwiązaniu nie rozumiesz :( To raczej nikt nie wie z czym pomóc.

---

Ogólnie to z tego co rozumiem to wychodzą nam dwie nierówności, następnie mamy zamienić jabłka i krowy na punkty : (xi​−ti​,xi​+ti​). Niestety nie do końca rozumiem dalszego rozwiązania. Co powinniśmy zrobić jak juz mamy te punkty?

Answer 1

Z tych dwóch otrzymanych nierówności wynika, że żeby krowa złapała jabłko, musi sie ono znajdować powyżej i na lewo krowy w układzie współrzędnych. Pozostają 2 pytania:

1. Czy jeżeli jabłko może być złapane przez 2 krowy A i B (B jest bardziej na prawo od A) to która krowa powinna je złapać?

Możemy założyć, że w optymalnym rozwiązaniu krowa B złapała jabłko. Ale nic nie stoi na przeszkodzie, żeby to jednak krowa A złapała to jabłko i rozwiązanie wciąż pozostanie optymalne. Sugeruje to, że możemy wybierać krowy zachłannie od lewej do prawej.

2. Jeśli zdecydujemy się żeby krowa C złapała jakieś jabłko, to które dokładnie powinna złapać?

Jasne jest, że krowy, które są wyżej mają potencjalnie mniejszy wybór jabłek niż krowy, które są niżej. W takim razie krowa C powinna wybierać najniżej położone jabłko, które może złapać, żeby nie podbierać jabłek innym krowom położonym wyżej.

Te obserwacja sugerują, że można przeglądać krowy posortowane od lewej do prawej i dla każdej wybierać najniżej położone jabłko.