您的位置: 首页  >  IT文章  >  [CSP-S模拟测试]:梦境（贪心+小根堆）

[CSP-S模拟测试]:梦境（贪心+小根堆）

分类: IT文章 • 2022-02-16 21:16:08

[CSP-S模拟测试]:梦境（贪心+小根堆）

题目描述

　　智者奥尔曼曾说过：有缘的人即使相隔海角天涯，也会在梦境中相遇。
　　$IcePrince\text{_}1968$和$IcePrincess\text{_}1968$便是如此。有一天$IcePrincess\text{_}1968$突发奇想：为什么不用梦境操控仪器来增加她和$IcePrince\text{_}1968$的缘分呢？
　　$IcePrincess\text{_}1968$的梦境可以用$n$个区间来表示，第$i$个区间$[l_i,r_i]$表示她的第$i$个梦境会在$l_i$时刻开始，在$r_i$时刻结束（包含$l_i$和$r_i$两个时刻）。因为$IcePrincess\text{_}1968$经常做白日梦，所以$n$可能很大。
　　两个人的梦境不是什么时候都能融合的。只有在一些关键的与另一个人相关的梦境转折点两个人的梦境相遇，才能完成融合，形成浪漫的梦境。$IcePrincess\text{_}1968$探测到$IcePrince\text{_}1968$近期的$m$个与$IcePrincess\text{_}1968$相关的梦境转折点，第$i$个转折点$t_i$表示他的第$i$个梦境转折点会在$t_i$时刻出现。因为$IcePrince\text{_}1968$和 $IcePrincess\text{_}1968$很有缘，$IcePrince\text{_}1968$经常梦到$IcePrincess\text{_}1968$，所以$m$可能会很大。
　　当$IcePrincess\text{_}1968$的一个梦境包含了$IcePrince\text{_}1968$的一个梦境转折点时，两个人的这两段梦境就能得到融合。但要注意$IcePrincess\text{_}1968$的每段梦境只能和 $IcePrince\text{_}1968$的一个梦境转折点融合，类似的，$IcePrince\text{_}1968$的每个梦境转折点只能和$IcePrincess\text{_}1968$的一段梦境融合，否则会引发时空混乱。
　　$IcePrincess\text{_}1968$很喜欢做和$IcePrince\text{_}1968$相关的梦。所以她想算出她的这些梦境最多能和$IcePrince\text{_}1968$的梦境转折点融合出多少个浪漫的梦境。$IcePrincess\text{_}1968$擅长文学但不擅长计算机，所以只能找你帮忙。

输入格式

　　输入文件名为$dream.in$。
　　文件的第一行为有两个正整数$n,m$，表示$IcePrincess\text{_}1968$的梦境个数和$IcePrince\text{_}1968$的与$IcePrincess\text{_}1968$相关的梦境转折点个数。
　　第$2$至第$n+1$行，每行两个正整数$l_i,r_i$，第$i+1$行的两个数刻画了$IcePrincess\text{_}1968$的第$i$段梦境，含义如题面中所述。
　　第$n+2$至第$n+m+1$行，每行一个正数$t_i$，第$i$行的两个数刻画了$IcePrince\text{_}1968$的第$i-n-1$个梦境转折点，含义如题面中所述。

输出格式

　　输出文件名和$dream.out$。
　　输出文件仅一行，一个非负整数$N$表示$IcePrincess\text{_}1968$最多能获得多少段浪漫的梦境。

样例

样例输入：

2 2
1 3
2 4
1
3

样例输出：

2

数据范围与提示

样例解释：

$IcePrincess\text{_}1968$可以将自己的第一段梦境和第一个梦境转折点匹配，第二段梦境和第二个梦境转折点匹配，从而获得两段浪漫的梦境。因为$IcePrincess\text{_}1968$一共只做了两个梦，所以这一定是最多的数量。

数据范围：

对于$30\%$的数据，$n\leqslant 10,m\leqslant 10$；
对于$50\%$的数据，$n\leqslant 100,m\leqslant 100$；
对于$70\%$的数据，$n\leqslant 2,000,m\leqslant 2,000$；
对于$100\%$的数据，$n\leqslant 200,000,m\leqslant 200,000,1\leqslant l_i,r_i\leqslant 1,000,000,000,1\leqslant ti\leqslant 1,000,000,000$，保证对于每段梦境，$l_i\leqslant r_i$。

题解

简单贪心。

将每段梦境按$l$从小到大排序，将每个梦境转折点从小到大排序。

枚举每个梦境转折点，并将每个$l$小于它的梦境压入一个以$r$排序的小根堆，然后弹走所有$r$已经小于它的梦境（因为梦境转折点递增，所以这些梦境已经没用了），然后选择$r$最小的这一个一定最优，统计有多少梦境转折点会被利用即可。

时间复杂度：$\Theta(n\log n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>
using namespace std;
struct rec{int l,r;}e[200001];
int n,m;
int t[200001],fail=1;
bool vis[200001];
int ans;
bool cmp(rec a,rec b){return a.l<b.l;}
priority_queue<int,vector<int>,greater<int>>q;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d%d",&e[i].l,&e[i].r);
	for(int i=1;i<=m;i++)scanf("%d",&t[i]);
	sort(e+1,e+n+1,cmp);
	sort(t+1,t+m+1);
	for(int i=1;i<=m;i++)
	{
		while(e[fail].l<=t[i]&&fail<=n){q.push(e[fail].r);fail++;}
		while(!q.empty()&&q.top()<t[i])q.pop();
		if(q.size()){ans++;q.pop();}
	}
	printf("%d",ans);
	return 0;
}

rp++

相关推荐