e901 - 婚姻介紹所
題目描述
題目給定 N 位男性和 N 位女性的適配積分，要求找出最多可以配對成功的數量，以及由此獲得的傭金總額。配對成功的條件是男性和女性的積分總和必須大於 10。
解題思路
本題可以使用貪心演算法解決。首先，分別對男性的積分和女性的積分進行排序。然後，使用兩個指針，一個指向積分最高的女性，一個從積分最低的男性開始遍歷。如果男性和女性的積分總和大于 10，則配對成功，將配對數量加一，並將女性指針向左移動。否則，男性指針向右移動。重複此過程，直到男性指針到達末尾。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
while(cin >> n){
if(n==0)break;
int a[n],b[n],ans=0;
for(int i=0;i<n;++i)
cin >> a[i];
for(int i=0;i<n;++i)
cin >> b[i];
sort(a,a+n);
sort(b,b+n);
for(int i=0,j=n-1;i<n;++i){
if(a[i]+b[j]>10){
++ans;
--j;
}
}
cout << ans << " " << ans*200 << "\n";
}
}