Porblem z zadaniem Frania

Question

Mam takie zdanie Frania
Moje rozwiązanie dostaje tylko 82 punkty

#include <bits/stdc++.h>

using namespace std;

class Cloth{
public:
    int claps;
    int id;
    int complet;

    Cloth (int claps, int id, int complet){
        this->claps = claps;
        this->id = id;
        this->complet = complet;
    }

    bool operator <(const Cloth & c) const{
        if (this->claps == c.claps)
            return this->id > c.id;
        else 
            return this->claps < c.claps;
    }
};

priority_queue<Cloth> pq;
vector<int> colors;
vector<int> days;
vector<int> seen(1e6 + 7, 0);

void load_days(int n){
    days.resize(n);
    for (int i = 0; i < n; i++){
        cin >> days[i];
        pq.push(Cloth(days[i] * 5, i, 3));
        pq.push(Cloth(days[i] * 3, i, 2));
        pq.push(Cloth(days[i] * 2, i, 1));
    }
}

void load_colors(int k){
    colors.resize(k);
    for (int i = 0; i < k; i++){
        cin >> colors[i];
    }
}

int find_min_use_claps(int k){
    vector<int> last_complet;
    int pointer = 0;

    while (!pq.empty()){
        Cloth cloth = pq.top();
        pq.pop();

        if (seen[cloth.id] == 3 || (cloth.complet == 2 && seen[cloth.id] == 2))
            continue;

        if (pointer == k)
            return -1;

        if (cloth.claps <= colors[pointer]){
            if (cloth.complet == 3)
                last_complet.push_back(cloth.id);
            seen[cloth.id] += cloth.complet;
            pointer++;
        }
        else if (cloth.complet != 3){ //jesli jest zbyt malo dla koszulek lub skarpetek 
            if (last_complet.empty()){
                return - 1;
            }
            else{ //jesli wczesniej byl moment gdzie koszulki i skarpetki dalismy do jednego koloru to w to miejsce dajemy aktualne ubranie
                int last_id = last_complet[last_complet.size()-1];
                seen[last_id] = 0;
                pq.push(Cloth(days[last_id] * 3, last_id, 2)); // dajemy na kolejke koszulki i skarpetki tej osoby u ktorej one sa powieszone na jednym kolorze
                pq.push(Cloth(days[last_id] * 2, last_id, 1));
                last_complet.pop_back();
            }
        }

    }
    return pointer;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    load_days(n);

    load_colors(k);

    sort(colors.begin(), colors.end(), greater<int>());

    int response = find_min_use_claps(k);

    if (response == -1)
        cout << "NIE\n";
    else 
        cout << response << "\n";

    return 0;
}

Nie umiem znaleźć testów dla których moje rozwiązanie jest błędne :(
Do tego znalazłem taki opis rozwiązania w internecie

Osobie, która gromadziła pranie przezd d dni, musimy przydzielić 5d klamerek jednego koloru albo 2d klamerek jednego i 3d innego koloru. Rozwiązanie zachłanne:
Sortujemy osoby nierosnąco po d, a liczby klamerek trzymamy w zbiorze.
Dla każdej kolejnej osoby o wymaganiu d, jeśli istnieje kolor zawierający co najmniej 5d klamerek, to używamy takiego koloru o najmniejszej możliwej liczbie klamerek,a w przeciwnym razie używamy dwóch kolorów zawierających odpowiednio co najmniej 3d i 2d klamerek, znów o najmniejszych możliwych liczbach klamerek.
Jeśli w jakimś przypadku żądany kolor nie istnieje, zwracamy NIE
Złożoność czasowa to O(nlogn), a pamięciowaO(n)

Nie wiem jak ze zbioru wyciągać tak wartości w takiej złożoności.

Tutaj piszą bardziej dokładnie na stronie 29, i jest napisane że można takie operacje robić na set z C++, tylko jak z niego wyciągać "najmniejszą możliwą ilość" ? A do tego set nie może zawierać duplikatów, a liczba klamerek tego samego koloru może się powtarzać, nic już z tego nie rozumiem.

 

 

Comments

Twój kod nie działa, bo pomysł jest zły. Nie możesz do jednego worka wrzucać to co jest konieczne z tym co jest opcjonalne. W sensie jeżeli czyjeś 5d claps będzie miało większą wartość niż kogoś innego 3d claps to "ukradnie" mu konieczne spinacze i nie starczy dla tego drugiego gościa, podczas gdy 5d można by rozbić na 3d i 2d i wtedy dla każdego by starczyło.

---

 Nie wiem czy dobrze cię rozumiem, mój program da dobre wyniki dla takich przypadków

            else{ //jesli wczesniej byl moment gdzie koszulki i skarpetki dalismy do jednego koloru to w to miejsce dajemy aktualne ubranie
                int last_id = last_complet[last_complet.size()-1];
                seen[last_id] = 0;
                pq.push(Cloth(days[last_id] * 3, last_id, 2)); // dajemy na kolejke koszulki i skarpetki tej osoby u ktorej one sa powieszone na jednym kolorze
                pq.push(Cloth(days[last_id] * 2, last_id, 1));
                last_complet.pop_back();
            }

Po prostu usunie wcześniejszą 5d i na jej miejsce da koszulki lub skarpetki, np dla danych

2 4

10 5

30 25 15 10

zwróci 4

jeśli źle cię zrozumiałem to proszę daj przykład dla którego mój program daje błędne wyniki :)

---

2 4

10 7

35 20 21 14

Po rozpisaniu:

50 30 20

35 21 14

Zostanie wzięte 35 i osoba 2 zostanie całkowicie obsłużona, jednak teraz nie da się obsłużyć osoby 1 bo 35 zostało już użyte, a pozostałe wartości są za małe. Nie testowałem czy rzeczywiście to nie zadziała, ale obstawiam, że właśnie to jest problemem.

---

wystarczy użyć ideone :)

https://ideone.com/D2FbPt

2 osoba zostanie obsłużona ponieważ wzięte 35 dla 2 zamieni na koszulki, od tego jest ten fragment kodu który wysłałem wyżej. Problem musi być jakaś inna sytuacja bo dla jednego testy gdzie bylo 500.000 dni i 1.000.000 kolorow, program powinien zwrocic 1.000.000 a mój zwracał NIE

Answer 1

Nie wiem jak naprawić Twój kod, ale mogę powiedzieć jak to zrobić korzystając z tych setów.

W c++ jest takie coś jak multiset, który działa jak zwykły set, ale pozwala na trzymanie duplikatów. Definiuje się go w zasadzie identycznie co set:

multiset<int> M;

I teraz możesz znaleźć najmniejszą liczbę większa lub równą x korzystając z lower_bound i to można zrobić w taki sposób:

multiset<int>::iterator it = M.lower_bound(x);

Jeżeli iterator it będzie równy M.end() to znaczy, że liczby większej/równej x nie ma, a w przeciwnym wypadku, znaczy że jest

Comments

Mam jakiś błąd, nie wiem czy dobrze usuwam wartości ze zbioru

#include <bits/stdc++.h>

using namespace std;

multiset<int> M;
vector<int> days;

void load_days(int n){
    days.resize(n);
    for (int i = 0; i < n; i++){
        cin >> days[i];
    }
}

void load_colors(int k){
    int color;
    for (int i = 0; i < k; i++){
        cin >> color;
        M.insert(color);
    }
}

int main(){
    int n, k, ans;
    ans = 0;
    cin >> n >> k;
    
    load_days(n);
    
    sort(days.begin(), days.end());
    
    load_colors(k);

    multiset<int>::iterator it;
    for (int i = 0; i < n; i++){
        it = M.lower_bound(days[i] * 5);
        if (it != M.end()){
            ans++;
            M.erase(it);
        }
        else{
            it = M.lower_bound(days[i] * 3);
            if (it != M.end()){
                ans++;
                M.erase(it);

                it = M.lower_bound(days[i] * 2);
                if (it != M.end()){
                    ans++;
                    M.erase(it);
                }
                else{
                    cout << "NIE\n";
                    return 0;
                }
            }
            else{
                cout << "NIE\n";
                return 0;
            }
        }
    }
    
    cout << ans << "\n";
    return 0;
}

dla testów przykładowych, idąc z debuggerem okazuje się że nie może znaleźć wartości dla koszulek osoby 2 (3 * 3 = 9)

---

days musi być posortowane nierosnąco

---

Dzięki kozaku!