P3615 如厕计划

    • 61通过
    • 583提交
  • 题目提供者 kkksc03 站长团
  • 评测方式 云端评测
  • 标签 贪心
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    竞赛比完之后,水箱里充满水的选手们鱼贯而出。凡华中学的厕所规划的很糟,只有两个厕位,于是厕所门前排起了长长的队伍。

    厕所有两个,一个是女生专用厕所,另一个是男女混用厕所。一共有2N个选手正在排队,男女生数量可能不同。如果队头的是妹子,只要某个厕所是空的就可以进入,但是如果两个厕所都是空的,那么优先进入女性专用厕所。而如果队头是个绅♂士,只有在男女混用厕所是空的时候才能使用;如果只有女性专用厕所是空的,那么队伍中最靠前的妹子就可以不用继续等直接如厕。我们假设所有人如厕都需要花1分钟,不考虑切换的时间。

    然而,N分钟后,就要开饭了,所有人必须如厕完,不过看样子似乎来不及。主办方可以重新调换顺序,不过有些人会因为新的顺序中自己更加后面了而感到不满,不满度是自己相比于原队列后退了几个顺序(除此之外跟自己的实际如厕顺序无关)。

    主办方发现了这一点,所以希望你帮助他们解决这个问题,设计出一种方案,对于其中不满意度最大的学生,尽可能让他的不满意度最小。你只需要告诉他门最不满意的学生的不满意度是多少。

    输入输出格式

    输入格式:

    由于人相当多,我们用几段字符串来描述这个队列。

    第一行一个整数N

    第二行一个整数M

    接下来M行,有一个字符串Si和一个整数Ki构成,中间有空格隔开,字符串中只有'M'(男)和'F'(女)。最后的字符串就是 S1拼接K1次+ S2拼接K2次+ ... +SM拼接KM次

    输出格式:

    输出一个整数,表示答案。如果无论怎么样都没办法N分钟之内达成,请输出-1

    输入输出样例

    输入样例#1: 复制
    5
    3
    FFF 1
    M 5
    FF 1
    输出样例#1: 复制
    2

    说明

    原队列是FFFMMMMMFF

    改进后的队列是FMMFFMMMFF

    所以厕所会按照下面的时间使用:

    分钟 1   2   3   4   5
    共用 2   3   6   7   8
    女用 1   4   5   9   10

    两个妹子往后面移动了2位,所以不满意度是2

    20% N<=10;M=1;K1=1

    40% N<=100000;M=1;K1=1

    100% 1<=N,Ki<=10^18;1<=M<=100000;所有Si字符串长度之和不超过200000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。