CSP 202212-2 训练计划

黎 浩然/ 19 8 月, 2023/ 算法/ALGORITHMS/ 0 comments

C++：100/100

#include "bits/stdc++.h"
using namespace std;

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

    int review_time[m + 1];
    int prerequisite[m + 1];
    vector<int> dependents[m + 1];

    for (int i = 1; i <= m; ++i) {
        cin >> prerequisite[i];
        if (prerequisite[i]) {
            dependents[prerequisite[i]].push_back(i);
        }
    }
    for (int i = 1; i <= m; ++i) {
        cin >> review_time[i];
    }

    int early_start_time[m + 1];
    int early_end_time[m + 1];
    bool availablility = true;
    for (int i = 1; i <= m; ++i) {
        if (!prerequisite[i]) {
            early_start_time[i] = 1;
            early_end_time[i] = review_time[i];
        } else {
            early_start_time[i] = early_end_time[prerequisite[i]] + 1;
            early_end_time[i] = early_start_time[i] + review_time[i] - 1;
        }
        if (early_end_time[i] > n) {
            availablility = false;
        }
    }

    int latest_start_time[m + 1];
    int latest_end_time[m + 1];
    if (availablility) {
        for (int i = m; i > 0; --i) {
            int tmp = n;
            for (int j: dependents[i]) {
                if (tmp >= latest_start_time[j]) {
                    tmp = latest_start_time[j] - 1;
                }
            }
            latest_end_time[i] = tmp;
            latest_start_time[i] = latest_end_time[i] - review_time[i] + 1;
        }
    }


    for (int i = 1; i <= m; ++i) {
        cout << early_start_time[i];
        if (i != m) {
            cout << " ";
        }
    }
    cout << endl;
    if (availablility) {
        for (int i = 1; i <= m; ++i) {
            cout << latest_start_time[i];
            if (i != m) {
                cout << " ";
            }
        }
        cout << endl;
    }
}