题目描述
牛牛举办了一场比赛,共有n支队伍来到现场参加比赛。该比赛共有m道题目,牛牛发现比赛的结果非常有意思,对于每一道题目。最终成功做出它的队伍都是连在一起的。即做出第i道题目的队伍是从$l_{i}$ 到$r_{i}$连号的。比赛结束后,牛牛准备为获奖队伍颁奖。由于比赛规则没有罚时这一项,为了保证相同AC数的队伍所获奖项相同,所以牛牛采取如下的方案颁奖。
首先是确定奖牌线,牛牛将所有参赛队伍按照最终通过题目总数降序排序。分别取排名为$\left \lceil \frac{n}{10} \right \rceil,\left \lceil \frac{n}{4} \right \rceil,\left \lceil \frac{n}{2} \right \rceil$ 队伍的通过题目总数作为金、银、铜的奖牌线。
$\left \lceil \; \; \right \rceil$为向上取整符,$\left \lceil x \right \rceil$表示大于等于x的最小正整数。
特别的,要求奖牌线不得少于1题,当所划奖牌线为0题时,应视为1题。
当某支队伍通过题目的总数大于等于金、银、铜对应奖牌线的题目数时,就获得对应的奖牌。
同时满足多个奖牌线要求时,取满足奖项中的最高奖项,例如同时满足金、银、铜时应颁发金牌,同时满足银、铜时颁发银牌。
请你模拟比赛的颁奖过程,最后输出获得金、银、铜牌的队伍数目。
输入描述
第一行输入两个正整数n,m$(1 \leq n \leq 10^9,0 \leq m \leq 10^5)$。
接下来输入m行,每行两个正整数$l_i,r_i(1 \leq l_i \leq r_i \leq n)$
表示通过每道题的队伍是哪一段区间。
输出描述
输出三个非负整数,表示最终获得金、银、铜牌的队伍数目。
样例
Input:
10 10
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
10 10
Output
1 2 2
说明
将所有参赛队伍按照最终通过题目总数降序排序后,通过题目为ac={10,9,8,7,6,5,4,3,2,1}ac=10,9,8,7,6,5,4,3,2,1
$\left \lceil \frac{10}{10} \right \rceil = 1,ac[1]=10$
$\left \lceil \frac{10}{4} \right \rceil = 3,ac[3]=8$
$\left \lceil \frac{10}{2} \right \rceil = 5,ac[5]=6$
金牌线10题,银牌线8题,铜牌线6题。
算法
扫描线/差分 $O(mlogm)$
如果不看数据范围,那么这一题就是一个裸的差分问题,但是这个数据范围显然不能用差分来解决。
转换一下思维,差分完其实不需要求出每个队伍答对了多少题,题目也没问这个,我们只需要求出答对k题的有多少队伍就行了。
在差分之后,就可以使用扫描线的思想,这里使用官方题解的图来说明:
- 对每道题的答题情况进行差分操作
2.引入扫描线
其实就是引入一个变量为维护当前的题目通过数,同时,我们将差分的两个端点存起来并排序,那么每两个相邻端点间的队伍当前的答题数量就是一样的,这样就可以维护答对k题的队伍的数量了。
3.扫描线的移动
遇到+1,now+1,下一个区间的题目ac数+1
遇到-1,抵消前面的+1
时间复杂度
O(mlogm)
C++ 代码
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 2e5+100, M = 1e5+100;
int n,m;
PII a[N]; //first 存放位置, second这个位置是 +1 还是 -1
int c[M]; //c[i] 表示做对i题的队伍有多少个
int main()
{
IO;
cin>>n>>m;
int l,r,cnt = 0;
for(int i = 0; i<m; i++){
cin>>l>>r; // 差分等价-> l位置+1 r+1位置-1
a[++cnt] = {l,1};
a[++cnt] = {r+1,-1};
}
sort(a+1,a+cnt+1);
int now = 0; //当前题目通过数
int mx = -1; //记录第一名的题目通过数
for(int i = 1; i<=cnt; i++){
if(a[i].x != a[i-1].x){ //更新c
c[now] += a[i].x - a[i-1].x; //这里不用+1
}
now += a[i].y; //更新到此为止题目通过数, 即扫描线扫到这里的值
mx = max(mx,now);
}
int au = 0, ag = 0,cu = 0;
for(int k = mx; k>=1; k--){
c[k] = c[k] + c[k+1] ; //c[k] 表示至少做对k题的队伍数量
if(!au && (c[k] >= (n+9)/10)) au = k; //注意上取整
if(!ag && (c[k] >= (n+3)/4)) ag = k;
if(!cu && (c[k] >= (n+1)/2)) cu = k;
}
au = max(1,au),ag =max(1,ag),cu = max(1,cu); //奖牌线最少1个
cout<<c[au]<<" "<<c[ag]-c[au]<<" "<<c[cu]-c[ag]<<endl;
return 0;
}