f446 - 1237 - Expert Enough
題目描述
題目給定 n 個工廠，每個工廠有名字和生產車子的最低和最高價格。接著給定 q 個詢問，每個詢問給定一個價格 p，要求找出生產車子價格區間包含 p 的工廠名。如果有多個工廠符合條件或沒有工廠符合條件，則輸出 "UNDETERMINED"。
解題思路
這題的解題思路是遍歷每個工廠，檢查其價格區間是否包含詢問的價格。如果找到唯一一個符合條件的工廠，則輸出該工廠的名字。如果找到多個符合條件的工廠或沒有符合條件的工廠，則輸出 "UNDETERMINED"。
複雜度分析
- 時間複雜度: O(t * d * q)，其中 t 是測資數，d 是工廠數，q 是詢問數。最壞情況下，需要遍歷所有工廠來檢查每個詢問。
- 空間複雜度: O(d)，其中 d 是工廠數。需要儲存所有工廠的資訊。
程式碼
#include <iostream>
using namespace std;
struct com{
string name;
int l,r;
};
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int t,d,q,dq;
cin >> t;
while(t--){
cin >> d;
com a[d];
for(int i=0;i<d;++i)
cin >> a[i].name >> a[i].l >> a[i].r;
cin >> dq;
for(int j=0;j<dq;++j){
cin >> q;
int ans,c=0;
for(int i=0;i<d;++i){
if(a[i].l<=q&&a[i].r>=q){
ans=i;
++c;
}
if(c>1)break;
}
if(c!=1)
cout << "UNDETERMINED\n";
else
cout << a[ans].name << "\n";
}
if(t)cout << "\n";
}
}