5.破译密码【算法赛】 - 蓝桥云课
问题描述
在近期举办的蓝桥杯竞赛中，诞生了一场激动人心的双人破译挑战。比赛的主办方准备了N块神秘的密码芯片，参赛队伍需要在这场智力竞赛中展示团队合作的默契与效率。每个队伍需选出一位破译者与一位传输者，破译者的任务是解锁芯片中隐藏的密码，而传输者则负责将微密后的密码准确无误地发送至主办方的电脑。
在这场比赛中，小蓝与小桥组参赛，经过深入的讨论与协商，小蓝被任命为破译者，专注于解密每一块密码芯片；而小桥则担任传输者，确保每一份信息能够迅速且顺畅地传递给裁判。比赛开始后，他们迅速评估了破译与传输每一块密码芯片所需的时间：小蓝破译第i块芯片需要A1：时间，而小桥则需要B1：时间来传输第i块芯片。
此时，小蓝和小桥迫切想要计算出，在最佳的策略下，完成所有密码芯片破译与传输所需的最短时间，请你帮帮他们。
注意：只有一块芯片完成破译后才能开始传输。
输入格式
第一行输入一个整数N（1≤N≤1000）表示芯片数量。
第二行输入N个整数A1, A2, A3, ···, AN (1≤A1≤10³) 表示小蓝破译每块芯片的时间。
第三行输入N个整数B1, B2, B3, ···, BN (1≤B1≤10³) 表示小桥传输每块芯片密码的时间。
输出格式
输出一个整数表示答案。
输入样例
4
1 3 5 7
6 5 1 4输出样例
17说明
两人可以按照（1，2，4，3）的芯片编号顺序进行破译传输，所需时间为17。
思路：
贪心，分两类
-
若
x属于 S1 组（x_s1 = true），y必定属于 S2 组（y_s1 = false）：-
返回
true→ 表示x应排在y前面。 -
结果：S1 组的
x排在 S2 组的y之前。
-
-
若
x属于 S2 组（x_s1 = false），y必定属于 S1 组（y_s1 = true）：-
返回
false→ 表示y应排在x前面。 -
结果：S1 组的
y排在 S2 组的x之前。
-
代码：
#include<bits/stdc++.h>
using namespace std;
int N;
struct Node{int a,b;
}num[1005];
int a[1005],b[1005];
bool compare(const Node & x,const Node & y)
{bool x_s1 = (x.a <= x.b);//x是否属于s1组 bool y_s1 = (y.a <= y.b);//y是否属于s1组 if(x_s1 != y_s1)//不同组 {return x_s1;//结果都是s1组在前面 }else//同组 要么s1组要么s2组 {if(x_s1 && y_s1)//如果同属s1 return x.a < y.a;//a升序排序 else//如果同属s2 return x.b > y.b;//b降序排序 }
}
int main(void)
{cin >> N;for(int i = 1 ; i <= N ; i++)cin >> a[i];for(int i = 1 ; i <= N ; i++)cin >> b[i];for(int i = 1 ; i <= N ; i++){num[i].a = a[i];num[i].b = b[i];}int sum_A = 0;int sum_B = 0;sort(num+1,num+1+N,compare);for(int i = 1 ; i <= N ; i++){sum_A += num[i].a;//先计算i的结束时间，也就是开始传输的时间 int cur_start = max(sum_A,sum_B);//利用最大值 sum_B = cur_start + num[i].b;//计算完成传输的最大时间 }cout << sum_B; return 0;} #include<bits/stdc++.h>
using namespace std;
int N;
struct Node{int a,b;
}num[1005];
int a[1005],b[1005];
bool compare(const Node & x,const Node & y)
{return min(x.a,y.b) < min(x.b,y.a);
}
int main(void)
{cin >> N;for(int i = 1 ; i <= N ; i++)cin >> a[i];for(int i = 1 ; i <= N ; i++)cin >> b[i];for(int i = 1 ; i <= N ; i++){num[i].a = a[i];num[i].b = b[i];}int sum_A = 0;int sum_B = 0;sort(num+1,num+1+N,compare);for(int i = 1 ; i <= N ; i++){sum_A += num[i].a;//先计算i的结束时间，也就是开始传输的时间 int cur_start = max(sum_A,sum_B);//利用最大值 sum_B = cur_start + num[i].b;//计算完成传输的最大时间 }cout << sum_B; return 0;} 