a535 - 10141 - Request for Proposal
題目描述
題目描述了政府或企業採購需求的情境。他們會發布 RFP (Request for Proposal)，廠商提交報價單，評估者根據廠商能滿足的需求數量和報價來選擇得標廠商。需求數量越多越好，如果數量相同則選擇報價最低的廠商。
解題思路
這題的核心是找到滿足最多需求的廠商，如果有多個廠商滿足相同數量的需求，則選擇報價最低的廠商。程式碼使用一個 Prop 結構體來儲存廠商的資訊，包括名稱、成本和滿足的需求數量。然後，程式碼遍歷所有廠商，並使用自定義的比較運算符 operator < 來比較廠商。比較運算符首先比較滿足的需求數量，如果數量相同，則比較成本。最後，程式碼輸出得標廠商的名稱。
複雜度分析
- 時間複雜度: O(npr)，其中 n 是需求項目數，p 是廠商數量，r 是每個廠商滿足的需求數量。最壞情況下，需要遍歷所有廠商的所有需求項目。
- 空間複雜度: O(n + p + r)，主要用於儲存需求項目、廠商資訊和每個廠商滿足的需求項目。
程式碼
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct Prop{
char name[82];
double cost;
int mark;
Prop(){mark = -1;};
};
inline bool operator < (const Prop &p1, const Prop &p2){
if(p1.mark != p2.mark)
return p1.mark < p2.mark;
return p1.cost > p2.cost;
}
int n,p;
int r;
string order[1024];
Prop prop;
string item[1024];
int main(){
for(int t = 1 ; ; t++)
{
Prop ans;
scanf("%d%d", &n, &p);
if(n==0 && p==0)
return 0;
getchar();
for(int i = 0 ; i < n ; i++)
getline(cin, order[0]);
for(int i = 0 ; i < p ; i++){
gets(prop.name);
scanf("%lf%d", &prop.cost, &prop.mark);
getchar();
for(int j = 0 ; j < prop.mark ; j++)
getline(cin, item[j]);
if(ans < prop)
ans = prop;
}
if(t > 1)
putchar('\n');
printf("RFP #%d\n",t);
printf("%s\n",ans.name);
}
return 0;
}