作者：foreverfda | 来源：互联网 | 2024-10-29 16:10
在CodeforcesGlobalRound3的B题"InherentTalent"中，主人公潇洒哥需要从A地前往C地，但两地之间没有直飞航班。他可以选择在A地和B地之间的中转航班，以便尽快抵达目的地C。该问题的核心在于如何合理安排中转，以实现最短的旅行时间。
Born This Way
原文链接：[传送门]
题目大意：潇洒哥想乘坐飞机从A地到达C地，但是没有直达的航班，在A地和B地之间有一个可以中转的航班B,潇洒哥想早点到达C地(有航班就坐)，但是很不幸他得罪了大魔王黑大帅，他可以取消潇洒哥的航班有k次机会(毕竟费蓝）让潇洒哥最迟到达，现在给你n,m,ta,tb,k分别表示为，A地到B地的行班数，B地到C地的行班数，A地到B地的需要的时间，B地到C地的时间，可以取消航班的次数，(连接时间可以忽略不计，因此只有当b j≥a i+ta时，才能使用a到b的第i次航班和b到c的第j次航班）求取消K次航班后最迟到达C地的时间，取消K次后不能到达C地输出-1。
代码：
1 #include"iostream"
2 #include"algorithm"
3 #include"cstdio"
4 #include"cstring"
5 using namespace std;
6 int n,m,ta,tb,k;
7 int a1[400005],b1[400005];
8 int main(){
9 std::ios::sync_with_stdio(false);
10 cin>>n>>m>>ta>>tb>>k;
11 for(int i=1;i<=n;i++) cin>>a1[i];
12 for(int j=1;j<=m;j++) cin>>b1[j];
13 if(k>=min(m,n)){
14 cout<<"-1"<<endl;
15 return 0;
16 }
17 int ans=0;
18 for(int i=1,j=1;i<=k+1;i++){
19 while(j<=m&&b1[j];
20 if(j+k-i+1>m){
21 cout<<"-1"<<endl;
22 return 0;
23 }
24 ans = max(ans,b1[j+k-i+1]+tb);
25 }
26 cout<endl;
27 return 0;
28 }
Codeforces Global Round 3:B. Born This Way
京公网安备 11010802041100号