d040 - 11207 - The easiest way
題目描述
題目要求從 N 張長方形紙張中選出最適合製作紙鳥的紙張。紙鳥需要正方形紙張，且需要製作 4 隻相同的紙鳥。目標是找到能製作出最大紙鳥的紙張，如果有多個最佳選擇，則輸出紙張的編號最小的那張。
解題思路
對於每張紙張，計算可以製作的最大正方形紙張的邊長。計算方式如下：
- 確保寬度小於等於高度。
- 如果高度大於等於寬度的 4 倍，則最大正方形邊長為寬度。
- 否則，如果高度大於等於寬度的 2 倍，則最大正方形邊長為高度除以 4。
- 否則，最大正方形邊長為寬度除以 2。 在計算完所有紙張的最大正方形邊長後，找到最大邊長，並輸出對應的紙張編號。如果有多個紙張具有相同的最大邊長，則輸出第一個出現的紙張編號。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
while(cin >> n){
if(n==0)break;
float a[n][3],ans=0;
for(int i=0;i<n;++i){
cin >> a[i][0] >> a[i][1];
if(a[i][0]>a[i][1]){
float tmp=a[i][0];
a[i][0]=a[i][1];
a[i][1]=tmp;
}
if(a[i][1]>=a[i][0]*4)
a[i][2]=a[i][0];
else if(a[i][1]>=a[i][0]*2)
a[i][2]=a[i][1]/4;
else
a[i][2]=a[i][0]/2;
ans=max(ans,a[i][2]);
}
for(int i=0;i<n;++i){
if(ans==a[i][2]){
cout << i+1 << "\n";
break;
}
}
}
}