BJTUOJ 1879 — OverCooked!

题目描述

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

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

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

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

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

题目链接

https://citel.bjtu.edu.cn/acm/problem/1879

输入数据

第 1 行 3 个整数 n, p, q (1≤n≤10^5, 1≤p, q≤100)。
接下来 n 行,第 i+1 行表示第 i 个订单,每个订单由一个字符串组成,该字符串的每个字符表示这个订单要求的一个原材料。
接下来 1 行,一个整数 m (1≤m≤10^5)。
接下来 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

题目分析

按照题目描述的过程进行模拟就行了。
数据量比较大,要使用 scanf 读取数据。

AC代码

#include <bits/stdc++.h>
using namespace std;
char cai[100005][6], cai2[100005][6];
int main()
{
    int n, p, t = 0, q, i, m, j, x = 0, ans = 0, len, len2;
    scanf("%d%d%d", &n, &p, &q);
    for (i = 0; i < n; i++)
        scanf("%s", cai[i]);
    scanf("%d", &m);

    for (i = 0; i < m; i++)
        scanf("%s", cai2[i]);
    for (i = 0, j = 0; j < m; j++)
    {
        len = strlen(cai[i]), len2 = strlen(cai2[j]);
        if (len != len2)
        {
            t = 0;
            x = 0;
            continue;
        }
        sort(cai[i], cai[i] + len);
        sort(cai2[j], cai2[j] + len);
        if (strcmp(cai[i], cai2[j]) == 0)
        {
            t = 1;
            x++;
            i++;
            ans += p;
            ans += (x - 1) * q;
        }
        else
        {
            t = 0;
            x = 0;
            continue;
        }
        if (i >= n)
            break;
    }
    printf("%d\n", ans);
    return 0;
}

2 个评论 在 “BJTUOJ 1879 — OverCooked!

  1. 无意间看到你的个人网站,第一感觉是好精巧,无处不在的二次元特点,非常可爱的网站(b站画风),谢谢你整理的题目,我们老师放在algo上的题目有些地方没有写清楚,看了你这儿就知道啦!我比较喜欢用java,当然有必要的话也会借鉴一下阁下的思路。
    这个网站真滴很棒!第一次见到,祝你学业有成,加油!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部