【BJTU-算法】 OverCooked！

2024-01-02 09:58

文章标签 算法 bjtu overcooked

本文主要是介绍【BJTU-算法】 OverCooked！，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

OverCooked!

餐厅中有 n 个订单，每个订单都是一道由指定原材料制成的菜。

订单必须依次完成，若上的菜符合当前订单的要求，订单完成并消失；若上的菜不符合当前订单的要求，订单会仍然存在。

每完成一个订单，均会获得 p 分，而连续成功完成订单可以获得小费作为分数奖励，连续第 x 个完成的订单可以获得 q×(x−1) 的额外分数。

所有订单全部完成后，再次上菜不获得任何分数。

鹦鹉厨师按照一定的顺序上了 m 道菜，他想知道自己最后获得了多少分数。

输入数据
第 1 行 3 个整数 n, p, q (1≤n≤100000, 1≤p, q≤100)。接下来 n 行，第 i+1 行表示第 i 个订单，每个订单由一个字符串组成，该字符串的每个字符表示这个订单要求的一个原材料。接下来 1 行，一个整数 m (1≤m≤100000)。接下来 m 行，第 n+i+2 行表示第 i 道菜，每道菜由一个字符串组成，该字符串的每个字符表示这个道菜包含的一个原材料。若上菜的原料集合和订单相同，即可算作完成订单要求。保证每个字符串长度不超过 4 且每个字符均为大写英文字母。例：若订单为 ABC，菜为 BAC，订单成功。若订单为 AAB，菜为 ABA，订单成功。若订单为 AAB，菜为 AA，订单失败。若订单为 AA，菜为 AAB，订单失败。

输出数据
输出一个数字为鹦鹉厨师最终获得的分数。

输入样例：

5 100 10
ABC
BB
A
C
BC
7
BAC
BBC
BC
BB
A
C
D

输出样例：

430

算法课简单的输入输出练习，顺便复习了一下string ：）
代码如下：

#include <bits/stdc++.h>using namespace std;
string a[100005];
string b[100005];
int f[100005];
int main()
{int n, p, q, m;long sum = 0;int h = 0;cin >> n >> p >> q;for (int i = 0; i < n; i++){cin >> a[i];sort(a[i].begin(), a[i].end());//给字符串排序，便于比较}cin >> m;for (int i = 0; i < m; i++){cin >> b[i];sort(b[i].begin(), b[i].end());if(b[i] == a[h]){sum += p;f[i] = 1;//标记菜完成h++;}}int cou = 0;for(int i = 0; i < m; i++){if(f[i] == 1){cou++;sum += q*(cou-1);}else cou = 0;}cout << sum;return 0;
}