f818 - 物競天擇 (Survival)

🔗 前往 ZeroJudge 原題

題目描述

題目給定兩個整數陣列 a 和 tmp，要求找到 a 中的一個元素 x 和 tmp 中的一個元素 y，使得 x * y 的值最小，並輸出 x 和 y 的值。

解題思路

這題可以使用貪心演算法解決。遍歷 tmp 陣列，對於每個 tmp[i]，遍歷 a 陣列，計算 a[j] * tmp[i] 的值。如果這個值比目前找到的最小值 ans 更小，則更新 ans，並記錄對應的 x 和 y 的值。最後輸出 x 和 y。

複雜度分析

• 時間複雜度: O(n^2)，其中 n 是陣列 a 和 tmp 的大小。因為需要嵌套循環遍歷兩個陣列。
• 空間複雜度: O(1)，只使用了常數個額外的變數。

程式碼

#include <iostream>
using namespace std;
int n,a[2001],ans=1000001,tmp,x,y;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> a[i];
	}
	for(int i=0;i<n;++i){
		cin >> tmp;
		if(tmp*a[i]<ans){
			ans=tmp*a[i];
			x=a[i];
			y=tmp;
		}
	}
	cout << x << " " << y;
}