73412024-01-07 21:39:03szabelrA lehető legkevesebb átszállás (50 pont)cpp17Elfogadva 50/509ms4116 KiB
#include <iostream>
#include <algorithm>

using namespace std;

struct VonatInfo {
    int sorszam;
    int start;
    int stop;
};

bool kisebbVonat(VonatInfo v1, VonatInfo v2) {
    return v1.start < v2.start;
}

int main() {

    VonatInfo A[10000];
    int hasznaltVonat[10000];
    int N, M;
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        int start, stop;
        cin >> start >> stop;
        A[i].sorszam = i + 1;
        A[i].start = start;
        A[i].stop = stop;
    }

    sort(A, A+N, kisebbVonat);

    int hol = 1, maxAllomas = 1;
    int K = 0;
    int i = 0;
    int maxHasznaltVonat;

    bool eljut = true;

    while (eljut && hol < M) {
        maxAllomas = hol;
        while (i<N and A[i].start <= hol) {
            if (A[i].stop >= maxAllomas) {
                maxAllomas = A[i].stop;
                maxHasznaltVonat = A[i].sorszam;
            }
            i++;
        }
        if (hol != maxAllomas) {
            hol = maxAllomas;
            hasznaltVonat[K++] = maxHasznaltVonat;
        }
        else {
            eljut = false;
        }
    }

    if (eljut) {
        cout << K-1 << endl;

        sort(hasznaltVonat, hasznaltVonat+K);
        for (int i = 0; i < K; i++) cout << hasznaltVonat[i] << " ";
    }
    else {
        cout << "-1";
    }

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms2028 KiB
2Elfogadva0/09ms2196 KiB
3Elfogadva1/13ms2276 KiB
4Elfogadva1/13ms2408 KiB
5Elfogadva2/23ms2632 KiB
6Elfogadva2/23ms2828 KiB
7Elfogadva2/23ms2908 KiB
8Elfogadva2/24ms3172 KiB
9Elfogadva2/24ms3112 KiB
10Elfogadva2/24ms3304 KiB
11Elfogadva2/24ms3280 KiB
12Elfogadva2/26ms3408 KiB
13Elfogadva2/23ms3316 KiB
14Elfogadva2/24ms3312 KiB
15Elfogadva2/24ms3312 KiB
16Elfogadva2/26ms3444 KiB
17Elfogadva2/27ms3528 KiB
18Elfogadva2/28ms3660 KiB
19Elfogadva2/28ms3740 KiB
20Elfogadva2/28ms3892 KiB
21Elfogadva2/29ms3744 KiB
22Elfogadva2/29ms3740 KiB
23Elfogadva2/28ms3872 KiB
24Elfogadva2/28ms3852 KiB
25Elfogadva2/28ms3980 KiB
26Elfogadva2/29ms4024 KiB
27Elfogadva2/29ms4116 KiB
28Elfogadva2/28ms4028 KiB