#P9712. 麻烦的杂货店
麻烦的杂货店
题目描述
一家杂货店卖一种零食,每袋 5 元。某天编号在区间 内的小学生按编号递增的顺序依次来店。每人只买一袋,并且只有一张固定面额的钞票。商店开门时没有零钱,只能用已经收到的 5 元钞票为付 10 元的人找零。关门时,收到的 5 元钞票必须全部用完。
店主可以选择只接待 内某个连续子区间的学生。她也可以当天一袋都不卖。求每天最多能卖出多少袋。
输入格式
第一行两个整数 ,分别是学生人数和天数。第二行一个长为 的字符串。第 个字符为 F 表示编号 的学生只有 5 元,为 T 表示只有 10 元。
接下来 行,每行两个整数 ,表示第 天来店学生的编号范围。
输出格式
输出 行。第 行是第 天能卖出的最大袋数。
样例
6 9
FTFTFT
1 2
3 4
5 6
1 4
3 6
1 6
1 3
1 4
1 5
2
2
2
4
4
6
2
4
4
原 PDF 输出行数中的 为笔误,按天数 输出。样例和本站评测均按此规则。
数据范围
,,。
对于 20% 的数据,。对于 40% 的数据,。对于 80% 的数据,。