k467 - 分班 (Class)
題目描述
題目給定一個包含 n 個學生的班級，以及 n 個學生的能力值。接著，題目會再給定 n 個學生的期望班級。目標是找出所有期望加入目前班級但能力值比班級學生低的學生，並將他們輸出。如果沒有任何學生符合條件，則輸出 -1。如果所有學生都期望加入目前班級，則輸出 -1。
解題思路
這題的解題思路是使用貪心演算法。首先，讀取班級學生的能力值。然後，迭代讀取每個學生的期望班級，並比較其能力值與目前班級學生的能力值。如果學生的能力值比班級學生低，則將其加入一個新的陣列中。最後，輸出新的陣列。如果新的陣列為空，則輸出 -1。如果新的陣列的長度等於 n，則輸出 -1。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int n,a[1005],x,m;
int main(){
cin >> n;
for(int i=1;i<=n;++i){
cin >> a[i];
}
for(int i=1;i<=n;++i){
cin >> x;
if(a[i]>x){
cout << i << " ";
}
else{
a[m++]=i;
}
}
if(m==n)cout << "-1\n";
else cout << "\n";
for(int i=0;i<m;++i){
cout << a[i] << " ";
}
if(m==0)cout << "-1";
}