題目

問題背景
西西艾弗島荒野求生大賽還有
天開幕！

問題描述
為了在大賽中取得好成績(jī)，頓頓準(zhǔn)備在
天時(shí)間內(nèi)完成“短跑”、“高中物理”以及“核裂變技術(shù)”等總共
項(xiàng)科目的加強(qiáng)訓(xùn)練。其中第
項(xiàng)（
）科目編號(hào)為
，也可簡(jiǎn)稱為科目
。已知科目
耗時(shí)
天，即如果從第
天開始訓(xùn)練科目
，那么第
天就是該項(xiàng)訓(xùn)練的最后一天。

大部分科目的訓(xùn)練可以同時(shí)進(jìn)行，即頓頓在同一天內(nèi)可以同時(shí)進(jìn)行多項(xiàng)科目的訓(xùn)練，但部分科目之間也存在著依賴關(guān)系。如果科目
依賴科目
，那么只能在后者訓(xùn)練結(jié)束后，科目
才能開始訓(xùn)練。具體來說，如果科目
從第
天訓(xùn)練到第
天，那么科目
最早只能從第
天開始訓(xùn)練。還好，頓頓需要訓(xùn)練的
項(xiàng)科目依賴關(guān)系并不復(fù)雜，每項(xiàng)科目最多只依賴一項(xiàng)別的科目，且滿足依賴科目的編號(hào)小于自己。那些沒有任何依賴的科目，則可以從第
天就開始訓(xùn)練。

對(duì)于每一項(xiàng)科目，試計(jì)算：

1）最早開始時(shí)間：該科目最早可以于哪一天開始訓(xùn)練？

2）最晚開始時(shí)間：在不耽誤參賽的前提下（
天內(nèi)完成所有訓(xùn)練），該科目最晚可以從哪一天開始訓(xùn)練？

天內(nèi)完成所有訓(xùn)練，即每一項(xiàng)科目訓(xùn)練的最后一天都要滿足
。需要注意，頓頓如果不能在
天內(nèi)完成全部
項(xiàng)科目的訓(xùn)練，就無法參加大賽。這種情況下也就不需要再計(jì)算“最晚開始時(shí)間”了。

輸入格式
從標(biāo)準(zhǔn)輸入讀入數(shù)據(jù)。

輸入共三行。

輸入的第一行包含空格分隔的兩個(gè)正整數(shù)
和
，分別表示距離大賽開幕的天數(shù)和訓(xùn)練科目的數(shù)量。

輸入的第二行包含空格分隔的
個(gè)整數(shù)，其中第
個(gè)（
）整數(shù)
表示科目
依賴的科目編號(hào)，滿足
；
表示科目
無依賴。

輸入的第三行包含空格分隔的
個(gè)正整數(shù)，其中第
個(gè)（
）數(shù)
表示訓(xùn)練科目
所需天數(shù)，滿足
。

輸出格式
輸出到標(biāo)準(zhǔn)輸出中。

輸出共一行或兩行。

輸出的第一行包含空格分隔的
個(gè)正整數(shù)，依次表示每項(xiàng)科目的最早開始時(shí)間。

如果頓頓可以在
天內(nèi)完成全部
項(xiàng)科目的訓(xùn)練，則繼續(xù)輸出第二行，否則輸出到此為止。

輸出的第二行包含空格分隔的
個(gè)正整數(shù)，依次表示每項(xiàng)科目的最晚開始時(shí)間。

代碼

AC

#include<bits/stdc++.h>
using namespace std;struct
{int form=0;//先導(dǎo)課int day=0;//消耗int start=1;//最早int last_start=0;//最晚 
}course[105]; int main()
{int max=-1;int n,m;cin>>n>>m;for(int i=0;i<m;i++){cin>>course[i].form;}for(int i=0;i<m;i++){cin>>course[i].day;}for(int i=0;i<m;i++){if(course[i].form != 0){course[i].start = course[course[i].form-1].start+course[course[i].form-1].day;//該門課的最早開始時(shí)間為先導(dǎo)課最早結(jié)束時(shí)間}cout<<course[i].start<<" ";//輸出最早開始時(shí)間 if((course[i].day+course[i].start)>max)//判斷是否能上完課 max=course[i].day+course[i].start-1;		}if(max<=n)//能上就輸出 {cout<<endl;for(int i=m-1;i>=0;i--){if(course[i].last_start==0)course[i].last_start=n-course[i].day+1;if(course[i].form != 0){int temp = course[i].last_start-course[course[i].form-1].day ;if(course[course[i].form-1].last_start == 0){course[course[i].form-1].last_start = temp ;}else{course[course[i].form-1].last_start = min(temp,course[course[i].form-1].last_start);}}}for(int i=0;i<m;i++){cout<<course[i].last_start<<" ";}}return 0;
}/*
14 7
0 1 0 3 2 3 0
2 1 6 3 10 4 3
*//*
51 5
0 1 2 3 4
10 10 10 10 10*/