j352 - 開心農場 (Farm)
題目描述
題目描述一個農場，農場有 n 個田地，每個田地有兩種作物產量。給定目標產量 x 和 y，要求找到最早的田地索引，使得累積產量分別達到或超過 x 和 y。如果無法達到目標產量，輸出 -1。最終輸出兩個田地索引的最大值加 1。
解題思路
這題使用貪心策略。分別對兩種作物進行迭代，計算累積產量，直到累積產量達到或超過目標產量。記錄下達到目標產量的田地索引。如果任何一種作物都無法達到目標產量，則輸出 -1。否則，輸出兩個田地索引的最大值加 1。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
int n,a[105][2],x,y,sx,sy,ansx=-1,ansy=-1;
int main(){
cin >> n;
for(int j=0;j<2;++j)
for(int i=1;i<=n;++i)
cin >> a[i][j];
cin >> x >> y;
for(int i=1;i<=n;++i){
sx+=a[i][0];
if(sx>=x){
ansx=i;
break;
}
}
for(int i=1;i<=n;++i){
sy+=a[i][1];
if(sy>=y){
ansy=i;
break;
}
}
if(ansx==-1||ansy==-1){
cout << "-1";
return 0;
}
else{
cout << max(ansx+1,ansy+1);
}
}