题意分析

1. 问题背景

• $RFP$（提案请求）：政府或企业发布的需求列表，供应商需提交满足部分或全部需求的提案。
• 提案评估：通过特性表（矩阵形式）记录每个提案满足的需求，最终按规则选择最优提案。

2. 输入输出要求

• 输入：
  • 每个$RFP$以两个整数$n$（需求数量）和$p$（提案数量）开始，输入$0\ 0$时终止。
  • 接下来的$n$行为需求名称（区分大小写）。
  • 每个提案信息包括：
    • 名称（字符串）。
    • 价格$d$（浮点数）和满足的需求数量$r$。
    • $r$个满足的需求名称（来自RFP列表，不重复）。
• 输出：
  • 对每个$RFP$，输出其编号（如$RFP$ #$1$）和最佳提案名称。
  • 选择标准优先级：
    1. 合规性最高（满足需求数$/$总需求数）。
    2. 价格最低（若合规性相同）。
    3. 输入顺序最先（若合规性和价格均相同）。

3. 关键概念

• 完全合规：满足所有需求（$r = n$）。
• 部分合规：$r < n$，按合规性公式$\text{合规性} = \frac{r}{n}$评估。

解题思路

1. 数据结构设计

• 需求存储：用集合或哈希表存储需求名称，便于快速检查提案是否满足某需求。
• 提案信息：存储每个提案的名称、价格、满足需求数$r$，并动态计算合规性$\frac{r}{n}$。

2. 算法流程

1. 读取$RFP$信息：
   • 读取$n$和$p$，若为$0\ 0$则终止程序。
   • 读取$n$个需求名称，存入集合。
2. 处理每个提案：
   • 记录提案名称、价格$d$和满足需求数$r$。
   • 检查$r$个需求是否合法（是否在$RFP$的需求集合中）。
   • 计算合规性$\frac{r}{n}$。
3. 选择最佳提案：
   • 完全合规优先：若有提案$r = n$，选择其中价格最低的；若价格相同，选择输入顺序最早的。
   • 部分合规处理：若无完全合规提案，选择合规性最高的提案；若合规性相同，按价格和输入顺序进一步筛选。

3. 边界与优化

• 输入顺序：需按输入顺序处理提案，确保最后能正确选择“最先出现”的提案。
• 浮点数比较：合规性计算可能涉及浮点数，建议用误差容忍比较（如$|a - b| < 10^{-6}$）。
• 效率：由于$n \leq 1000$且$p$无明确限制，算法时间复杂度为$O(p \cdot n)$，可通过哈希优化需求检查。

标程

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1000;
char P[N + 1][1000];  // 用二维字符数组代替 string 数组，假设每个字符串长度不超过 1000
char name[1000], ans[1000];  // 定义字符数组来存储字符串

int main()
{
    int n, p, caseno = 0;
    while (~scanf("%d%d", &n, &p) && (n || p)) {
        getchar();
        for (int i = 0; i < n; i++) {
            fgets(P[i], sizeof(P[i]), stdin);  // 使用 fgets 读取字符串，注意 fgets 会读取换行符
            P[i][strcspn(P[i], "\n")] = '\0';  // 手动去除换行符
        }

        int num, maxcnt = 0;
        double cost = 0.0, price;
        for (int i = 0; i < p; i++) {
            fgets(name, sizeof(name), stdin);
            name[strcspn(name, "\n")] = '\0';  // 手动去除换行符
            scanf("%lf%d", &price, &num);
            getchar();

            int cnt = 0;
            for (int j = 0; j < num; j++) {
                char tmp[1000];  // 定义字符数组存储临时字符串
                fgets(tmp, sizeof(tmp), stdin);
                tmp[strcspn(tmp, "\n")] = '\0';  // 手动去除换行符
                cnt++;
            }
            if (cnt > maxcnt) {
                maxcnt = cnt;
                cost = price;
                strcpy(ans, name);  // 复制字符串
            } else if (cnt == maxcnt) {
                if (cost > price) {
                    cost = price;
                    strcpy(ans, name);  // 复制字符串
                }
            }
        }

        if (caseno++) printf("\n");
        printf("RFP #%d\n%s\n", caseno, ans);
    }

    return 0;
}