Zadanie prawnicy XXV OI

Question

Cześć,

Robię zadanie Prawnicy z 1 etapu XXV OI https://szkopul.edu.pl/problemset/problem/KkN5UonnNGIG3AuMqoI6xr62/site/?key=statement

Napisałem taki kod:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Prawnik
{
    int poczatek;
    int koniec;
    int numer_prawnika;

    bool operator < (const Prawnik &prawnik) const
    {
        if (poczatek == prawnik.poczatek)
            return koniec < prawnik.koniec;
        return poczatek < prawnik.poczatek;
    }
};

int n = 0, k = 0, a = 0, b = 0, max_wyn = 0, poczatek = 0, koniec = 0, wskaznik = 0, wyn_i = 0, wyn_j = 0, ile_mamy = 0;
vector<Prawnik> prawnicy;

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

    cin >> n >> k;

    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b;
        prawnicy.push_back({a,b,i+1});
    }
    sort(prawnicy.begin(),prawnicy.end());

    for (int i = 0; i < n; ++i)
    {
        vector<int> pasujace;
        poczatek = prawnicy[i].poczatek;
        for (int f = 0; f < n; ++f)
        {
            if (prawnicy[f].poczatek <= poczatek)
            {
                if (prawnicy[f].koniec >= poczatek)
                    pasujace.push_back(prawnicy[f].koniec);
            }
            else
                break;
        }
        sort(pasujace.begin(),pasujace.end());
        if (pasujace.size() >= k)
        {
            koniec = pasujace[pasujace.size()-k];
            if (koniec - poczatek > max_wyn)
            {
                max_wyn = koniec-poczatek;
                wyn_i = poczatek;
                wyn_j = koniec;
            }
        }
    }

    printf("%d \n",max_wyn);
    for (int i = 0; i < n; ++i)
    {
        if (prawnicy[i].poczatek <= wyn_i && prawnicy[i].koniec >= wyn_j && ile_mamy < k)
        {
            printf("%d ",prawnicy[i].numer_prawnika);
            ile_mamy++;
        }
    }

    return 0;
}

Przeszedł na 50 pkt, bo złożonność jest kwadratowa. Zliczam jakie przedziały zaczynają się na początku <= sprawdzanemu i ich koniec >= poczatkowy. Da się jakoś ulepszyć to rozwiązanie lub zrobić jakieś inne?

Nie znalazłem nigdzie w necie rozwiązania do tego zadania.

Z góry dziękuję za pomoc i poświęcony czas!

Comments

hint: gąsienica

---

a coś troszeczkę więcej?

---

Jak wiesz że na przedziale [i, j] jest >= k pracowników to możesz tak naprawde przesuwać ten prawy koniec przedziału (czyli j) tak długo aż warunek >= jest spełniony. Co zrobić gdy przesuneliśmy to j tak daleko jak mogliśmy i po przesunięciu o jescze jeden w prawo warunek przestał być spełniony?

---

Niekoniecznie, np. dla testu przykładowego taka tablica by wyglądała tak : 1 2 3 4 5 4 4 3 2 1 2 0 z czego wynika, że odpowiedź wynosiłaby 6.

Answer 1

Wróciłem wczoraj do tego zadania i napisałem zamiatanie. Sortuję prawników po początkach, i teraz jeśli w spotkaniu ma uczestniczyć i-ty prawnik, to muszę znaleźć k-1 prawników, których początki są <= początkowi i-tego prawnika. I chcę, żęby były jak największe(wtedy spotkanie jest tym dłuższe). Robię to łatwo jak przetwarzam i-tego prawnika, to dodaję jego koniec na multiseta / seta(tylko mogą być powtórzenia, więc chyba trzeba structa jak się chce seta) / kolejkę priorytetową i cały myk polega na tym, że trzymam na niej K największych wyników o końcu >= początkowi i-tego prawnika, a początki są posortowane!. O(N lg N), ze względu na sortowanie i operacje na multisecie / secie / kolejce priorytetowej. Potem trzeba odtworzyć którzy to prawnicy znając max wyn, to można sobie puścić ten sam algorytm, tylko jak dodajemy na seta / multiseta / kolejkę priorytetową, to zamiat końca(int-a) np. robimy structa: wartośc i idx. Oczywiście przy sortowaniu trzeba zapamiętać idx danego prawnika. Kod dający 100:

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

struct Przedzial
{
    int poczatek;
    int koniec;
    int idx;
    bool operator < (const Przedzial &przedzial) const
    {
        return poczatek < przedzial.poczatek;
    }
};

struct Element
{
    int wartosc;
    int idx;
    bool operator < (const Element &element) const
    {
        if (wartosc == element.wartosc)
            return idx < element.idx;
        return wartosc < element.wartosc;
    }
};

int n = 0, k = 0, wyn = 0;
vector<Przedzial> przedzialy;
multiset<int> S;
set<Element> S_odtw;

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

    cin >> n >> k;

    przedzialy.assign(n,{});
    for (int i = 0; i < n; ++i)
    {
        cin >> przedzialy[i].poczatek >> przedzialy[i].koniec;
        przedzialy[i].idx = i+1;
    }

    sort(przedzialy.begin(), przedzialy.end());

    for (int i = 0; i < n; ++i)
    {
        while(!S.empty())
        {
            if (*S.begin() < przedzialy[i].poczatek)
                S.erase(S.lower_bound(*S.begin()));
            else
                break;
        }
        S.insert(przedzialy[i].koniec);
        if (S.size() > k)
            S.erase(S.lower_bound(*S.begin()));
        if (S.size() == k)
            wyn = max(wyn, *S.begin() - przedzialy[i].poczatek);
    }

    for (int i = 0; i < n; ++i)
    {
        while(!S_odtw.empty())
        {
            if (S_odtw.begin()->wartosc < przedzialy[i].poczatek)
                S_odtw.erase(*S_odtw.begin());
            else
                break;
        }
        S_odtw.insert({przedzialy[i].koniec,przedzialy[i].idx});
        if (S_odtw.size() > k)
            S_odtw.erase(*S_odtw.begin());
        if (S_odtw.size() == k)
        {
            if (S_odtw.begin()->wartosc - przedzialy[i].poczatek == wyn)
            {
                cout << wyn << '\n';
                while(!S_odtw.empty())
                {
                    cout << S_odtw.begin()->idx << ' ';
                    S_odtw.erase(*S_odtw.begin());
                }
                return 0;
            }
        }
    }

    return 0;
}