A27719. 老鼠爱美食(mouse)
填空题
中等
知识点
题目描述
老鼠爱美食(mouse)
题目描述
在一条道路上有很多从 1 开始依次编号的老鼠最爱的美食，假设每种美食都有无限多，而老鼠们随机闪现在任一个美食旁，然后依次尝试美食，至少需要尝试到第一次出现时的下一个美食为止，求哪两种相邻的美食被老鼠们尝试的次数最多，输出最多的次数即可。保证每只老鼠出现和停止的美食编号都不同。
输入
输入数据有 n+1 行，第一行表示老鼠数量 n，接下来 n 行每行都有两个数，分别表示老鼠第一次出现的美食编号，和停止的美食编号
输出
一行一个正整数，表示最多的次数。
样例输入
3
1 4
2 5
3 7
样例输出
3
样例解释
共有 3 只老鼠，第一只依次尝试了 1-2-3-4 共 4 种美食；第二只依次尝试了2-3-4-5 共 4 种美食；第三只依次尝试了 3-4-5-6-7 共 5 种美食。相邻的 3-4 美食被尝试了 3 次。
数据范围：2≤n≤10000，
美食种类保证在 int 范围内，每只老鼠出现和停止的美食编号都不同。
参考答案
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
int l, r;
map <int, int> mp;
for(int i = 0; i < n; i++) {
scanf("%d%d", &l, &r);
mp[l]++, mp[r+1]--;
}
int ans = 0, cur = 0;
for(auto &i:mp) {
cur += i.second;
ans = max(ans, cur);
}
printf("%d", ans);
return 0;
}
上一题
下一题