CCF-CSP认证考试 202212-2 训练计划 100分题解

更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202212-2 训练计划

时间限制： 1.0s
内存限制： 512.0MB

问题背景

西西艾弗岛荒野求生大赛还有 $n$ 天开幕！

问题描述

为了在大赛中取得好成绩，顿顿准备在 $n$ 天时间内完成“短跑”、“高中物理”以及“核裂变技术”等总共 $m$ 项科目的加强训练。其中第 $i$ 项（ $\le i \le m$ ）科目编号为 $i$ ，也可简称为科目 $i$ 。已知科目 $i$ 耗时 $t_i$ 天，即如果从第 $a$ 天开始训练科目 $i$ ，那么第 $a + t_i - 1$ 天就是该项训练的最后一天。

大部分科目的训练可以同时进行，即顿顿在同一天内可以同时进行多项科目的训练，但部分科目之间也存在着依赖关系。如果科目 $i$ 依赖科目 $j$ ，那么只能在后者训练结束后，科目 $i$ 才能开始训练。具体来说，如果科目 $j$ 从第 $a$ 天训练到第 $a + t_j - 1$ 天，那么科目 $i$ 最早只能从第 $a + t_j$ 天开始训练。还好，顿顿需要训练的 $m$ 项科目依赖关系并不复杂，每项科目最多只依赖一项别的科目，且满足依赖科目的编号小于自己。那些没有任何依赖的科目，则可以从第 $1$ 天就开始训练。

对于每一项科目，试计算：

1）最早开始时间：该科目最早可以于哪一天开始训练？

2）最晚开始时间：在不耽误参赛的前提下（ $n$ 天内完成所有训练），该科目最晚可以从哪一天开始训练？

$n$ 天内完成所有训练，即每一项科目训练的最后一天都要满足 $\le n$ 。需要注意，顿顿如果不能在 $n$ 天内完成全部 $m$ 项科目的训练，就无法参加大赛。这种情况下也就不需要再计算“最晚开始时间”了。

输入格式

从标准输入读入数据。

输入共三行。

输入的第一行包含空格分隔的两个正整数 $n$ 和 $m$ ，分别表示距离大赛开幕的天数和训练科目的数量。

输入的第二行包含空格分隔的 $m$ 个整数，其中第 $i$ 个（ $\le i \le m$ ）整数 $p_i$ 表示科目 $i$ 依赖的科目编号，满足 $\le p_i < i$ ； $p_i = 0$ 表示科目 $i$ 无依赖。

输入的第三行包含空格分隔的 $m$ 个正整数，其中第 $i$ 个（ $\le i \le m$ ）数 $t_i$ 表示训练科目 $i$ 所需天数，满足 $\le t_i \le n$ 。

输出格式

输出到标准输出中。

输出共一行或两行。

输出的第一行包含空格分隔的 $m$ 个正整数，依次表示每项科目的最早开始时间。

如果顿顿可以在 $n$ 天内完成全部 $m$ 项科目的训练，则继续输出第二行，否则输出到此为止。

输出的第二行包含空格分隔的 $m$ 个正整数，依次表示每项科目的最晚开始时间。

样例 1 输入

10 5
0 0 0 0 0
1 2 3 2 10

样例 1 输出

1 1 1 1 1
10 9 8 9 1

样例 1 说明

五项科目间没有依赖关系，都可以从第 $1$ 天就开始训练。

$10$ 天时间恰好可以完成所有科目的训练。其中科目 $1$ 耗时仅 $1$ 天，所以最晚可以拖延到第 $10$ 天再开始训练；而科目 $5$ 耗时 $10$ 天，必须从第 $1$ 天就开始训练。

样例 2 输入

10 7
0 1 0 3 2 3 0
2 1 6 3 10 4 3

样例 2 输出

1 3 1 7 4 7 1

样例 2 说明

七项科目间的依赖关系如图所示，其中仅科目 $5$ 无法在 $10$ 天内完成训练。

具体来说，科目 $5$ 依赖科目 $2$ 、科目 $2$ 又依赖于科目 $1$ ，因此科目 $5$ 最早可以从第 $4$ 天开始训练。

样例 3 输入

10 5
0 1 2 3 4
10 10 10 10 10

样例 3 输出

1 11 21 31 41

子任务

$70\%$ 的测试数据满足：顿顿无法在 $n$ 天内完成全部 $m$ 项科目的训练，此时仅需输出一行“最早开始时间”；

全部的测试数据满足 $\le 365$ 且 $\le 100$ 。

题解

感觉第二题不太会考拓扑，但是这题拓扑序太典了，然后也没有搜到官方的讲题视频，不知道本意是考什么，就直接写拓扑了。

对于最早开始时间：如果科目 $i$ 依赖于科目 $j$ ，即要先训练 $j$ 才能训练 $i$ ，那么就连一条 $j\to i$ 的有向边。所有入度为 $0$ 的科目都不存在依赖的科目，可以在第 $1$ 天直接开始训练。其他的科目都要在其依赖的科目训练完后才能训练。执行拓扑的时候，当执行到边 $j\to i$ 时，用 $mn_j+t_j$ 更新（取最大值） $mn_i$ ，最后即可求出最早开始时间。

求出所有科目的最早开始时间后，可以很容易求出最早结束时间为 $mn + t$ ，将其与 $n$ 进行判断，如果大于 $n$ 的话，就无法在 $n$ 天内训练完 $m$ 个科目，可以直接退出。

对于最晚开始时间：考虑反图，即如果科目 $i$ 依赖于科目 $j$ ，即要先训练 $j$ 才能训练 $i$ ，那么就连一条 $i\to j$ 的有向边。所有入度为 $0$ 的科目由于没有被依赖的科目，都可以在最后一刻完成，即 $mx_i=n-t_i+1$ 。其他的科目都要在其被依赖科目的最晚开始时间前完成训练。执行拓扑的时候，当执行到边 $i\to j$ 时，用 $mx_i-t_j$ 更新（取最小值） $mx_j$ ，最后即可求出最晚开始时间。

时间复杂度： $\mathcal{O}(m)$ 。

参考代码（15ms，12.64MB）

/*
    Created by Pujx on 2024/3/25.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include "debug.h"
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int a[N];
int n, m, t, k, q;

vector<int> g[N], ginv[N];
int in[N], out[N], mn[N], mx[N];

void work() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> t;
        if (!t) continue;
        g[t].emplace_back(i), in[i]++;
        ginv[i].emplace_back(t), out[t]++;
    }
    cinarr(a, m);

    queue<int> q;
    for (int i = 1; i <= m; i++)
        if (!in[i]) mn[i] = 1, q.push(i);
    int x = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v : g[u]) {
            mn[v] = max(mn[v], mn[u] + a[u]);
            if (!--in[v]) q.push(v);
        }
        x = max(x, mn[u] + a[u] - 1);
    }
    coutarr(mn, m);
    if (x > n) return;

    mem(mx, 0x3f);
    for (int i = 1; i <= m; i++)
        if (!out[i]) mx[i] = n - a[i] + 1, q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v : ginv[u]) {
            mx[v] = min(mx[v], mx[u] - a[v]);
            if (!--out[v]) q.push(v);
        }
    }
    coutarr(mx, m);
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

关于代码的亿点点说明：

代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。
#pragma ... 是用来开启 O2、O3 等优化加快代码速度。
中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。
"debug.h" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。
将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。