124822024-12-19 08:16:16feheristvanA lehető legkevesebb átszállás (50 pont)cpp17Hibás válasz 2/508ms760 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct vonat {
    int kezd, veg, ind;  // Starting time, ending time, and index of the train
};

// Function to compare trains by start time (and end time in case of tie)
bool compare(vonat a, vonat b) {
    return a.kezd < b.kezd;
}

int main() {
    long n, m;
    cin >> n >> m;

    vector<vonat> trains(n); // Vector to hold train schedules

    // Input train data
    for (int i = 0; i < n; i++) {
        cin >> trains[i].kezd >> trains[i].veg;
        trains[i].ind = i + 1;  // Store the index of the train
    }

    // Sort trains by start time, and by end time in case of tie
    sort(trains.begin(), trains.end(), compare);

    vector<int> selected_trains;  // Vector to store indices of selected trains
    int current_end = 0;          // The current position we need to reach
    int idx = 0;                  // Index for traversing the trains
    int farthest = 0;             // The farthest we can reach with the current train sequence

    // Greedily pick the minimum number of trains
    while (current_end < m) {
        // Find the farthest train that starts before or at current_end
        while (idx < n && trains[idx].kezd <= current_end) {
            farthest = max(farthest, trains[idx].veg);
            idx++;
        }

        // If no train can extend our reach, we are stuck
        if (farthest <= current_end) {
            cout << -1 << endl;
            return 0;
        }

        // Move to the farthest position and add this train to the selection
        current_end = farthest;
        selected_trains.push_back(trains[idx - 1].ind);  // Store the index of the selected train
    }

    // Output the count of trains and their indices
    cout << selected_trains.size() << endl;
    for (int i = 0; i < selected_trains.size(); i++) {
        cout << selected_trains[i] << " ";
    }
    cout << endl;

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base2/50
1Hibás válasz0/01ms320 KiB
2Hibás válasz0/08ms320 KiB
3Elfogadva1/11ms500 KiB
4Elfogadva1/11ms320 KiB
5Hibás válasz0/21ms320 KiB
6Hibás válasz0/21ms320 KiB
7Hibás válasz0/21ms320 KiB
8Hibás válasz0/22ms320 KiB
9Hibás válasz0/22ms320 KiB
10Hibás válasz0/23ms384 KiB
11Hibás válasz0/23ms320 KiB
12Hibás válasz0/24ms500 KiB
13Hibás válasz0/21ms500 KiB
14Hibás válasz0/22ms424 KiB
15Hibás válasz0/23ms360 KiB
16Hibás válasz0/24ms396 KiB
17Hibás válasz0/26ms484 KiB
18Hibás válasz0/26ms500 KiB
19Hibás válasz0/27ms504 KiB
20Hibás válasz0/28ms320 KiB
21Hibás válasz0/28ms320 KiB
22Hibás válasz0/28ms572 KiB
23Hibás válasz0/27ms320 KiB
24Hibás válasz0/27ms500 KiB
25Hibás válasz0/27ms320 KiB
26Hibás válasz0/27ms348 KiB
27Hibás válasz0/27ms320 KiB
28Hibás válasz0/27ms760 KiB