5.破譯密碼【算法賽】 - 藍橋云課

問題描述

在近期舉辦的藍橋杯競賽中，誕生了一場激動人心的雙人破譯挑戰。比賽的主辦方準備了N塊神秘的密碼芯片，參賽隊伍需要在這場智力競賽中展示團隊合作的默契與效率。每個隊伍需選出一位破譯者與一位傳輸者，破譯者的任務是解鎖芯片中隱藏的密碼，而傳輸者則負責將微密后的密碼準確無誤地發送至主辦方的電腦。

在這場比賽中，小藍與小橋組參賽，經過深入的討論與協商，小藍被任命為破譯者，專注于解密每一塊密碼芯片；而小橋則擔任傳輸者，確保每一份信息能夠迅速且順暢地傳遞給裁判。比賽開始后，他們迅速評估了破譯與傳輸每一塊密碼芯片所需的時間：小藍破譯第i塊芯片需要A1：時間，而小橋則需要B1：時間來傳輸第i塊芯片。

此時，小藍和小橋迫切想要計算出，在最佳的策略下，完成所有密碼芯片破譯與傳輸所需的最短時間，請你幫幫他們。

注意：只有一塊芯片完成破譯后才能開始傳輸。

輸入格式

第一行輸入一個整數N（1≤N≤1000）表示芯片數量。

第二行輸入N個整數A1, A2, A3, ···, AN (1≤A1≤103) 表示小藍破譯每塊芯片的時間。

第三行輸入N個整數B1, B2, B3, ···, BN (1≤B1≤103) 表示小橋傳輸每塊芯片密碼的時間。

輸出格式

輸出一個整數表示答案。

輸入樣例

4
1 3 5 7
6 5 1 4

輸出樣例

17

說明

兩人可以按照（1，2，4，3）的芯片編號順序進行破譯傳輸，所需時間為17。

思路：

貪心，分兩類

1. 若?x?屬于 S1 組（x_s1 = true），y?必定屬于 S2 組（y_s1 = false）：

   • 返回?true?→ 表示?x?應排在?y?前面。

   • 結果：S1 組的?x?排在 S2 組的?y?之前。

2. 若?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;}