c语言实现:餐厅中有 n 个订单,每个订单都是一道由指定原材料制成的菜。 订单必须依次完成,若上的菜符合当前订单的要求,订单完成并消失;若上的菜不符合当前订单的要求,订单会仍然存在。 每完成一个订单,均会获得 p 分,而连续成功完成订单可以获得小费作为分数奖励,连续第 x 个完成的订单可以获得 q×(x−1) 的额外分数。 所有订单全部完成后,再次上菜不获得任何分数。 鹦鹉厨师按照一定的顺序上了 m 道菜,他想知道自己最后获得了多少分数。 输入数据 第 1 行 3 个整数 n, p, q (1≤n≤105, 1≤p, q≤100)。 接下来 n 行,第 i+1 行表示第 i 个订单,每个订单由一个字符串组成,该字符串的每个字符表示这个订单要求的一个原材料。 接下来 1 行,一个整数 m (1≤m≤105)。 接下来 m 行,第 n+i+2 行表示第 i 道菜,每道菜由一个字符串组成,该字符串的每个字符表示这个道菜包含的一个原材料。 若上菜的原料集合和订单相同,即可算作完成订单要求。 保证每个字符串长度不超过 4 且每个字符均为大写英文字母。 例: 若订单为 ABC,菜为 BAC,订单成功。 若订单为 AAB,菜为 ABA,订单成功。 若订单为 AAB,菜为 AA,订单失败。 若订单为 AA,菜为 AAB,订单失败。 输出数据 输出一个数字为鹦鹉厨师最终获得的分数。
时间: 2023-05-22 08:02:01 浏览: 88
菜单的实现 c语言
以下是C知道的回答:
这道题可以使用哈希表来解决。首先将每个订单中的原材料存储到一个哈希表中,然后遍历每道菜,如果菜中的原材料也在哈希表中,就将该原材料从哈希表中删除。如果哈希表为空,说明当前订单已经完成,可以获得 p 分和连续完成订单的小费。同时,如果当前是第 x 个连续完成的订单,还可以获得额外的 q×(x−1) 分。最后将所有得分相加即可。
以下是代码实现:
#include <stdio.h>
#include <string.h>
#define MAX_N 100005
#define MAX_M 100005
#define MAX_LEN 5
int n, p, q, m;
char order[MAX_N][MAX_LEN];
char dish[MAX_M][MAX_LEN];
int order_hash[26];
int cnt, last_cnt;
int ans;
int main() {
scanf("%d%d%d", &n, &p, &q);
for (int i = 0; i < n; i++) {
scanf("%s", order[i]);
for (int j = 0; j < strlen(order[i]); j++) {
order_hash[order[i][j] - 'A']++;
}
}
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%s", dish[i]);
cnt = 0;
for (int j = 0; j < strlen(dish[i]); j++) {
if (order_hash[dish[i][j] - 'A'] > 0) {
order_hash[dish[i][j] - 'A']--;
cnt++;
}
}
if (cnt == strlen(order[last_cnt])) {
ans += p + q * last_cnt;
last_cnt++;
if (last_cnt == n) {
break;
}
} else if (cnt > 0) {
for (int j = 0; j < cnt; j++) {
order_hash[dish[i][j] - 'A']++;
}
}
}
printf("%d\n", ans);
return 0;
}
阅读全文