HDU5124lines题解-堆+贪心的一个新方法

题目链接

https://cn.vjudge.net/problem/HDU-5124

胡扯

感觉说新方法好像有点不太好,但是翻了十几篇博客都是清一色离散化之类的...

为什么会做这道题呢?因为前几天做了套NOIp模拟赛,T1是坐标轴上的最大团,愉快地转化成最多不相交区间问题贪心处理

但是我把大于等于号看反了，以为区间相交才连边，于是转化成了"让你找出被覆盖次数最多的点(线段)被覆盖的次数"，也就是这题

然后考场上yy出了一个堆+贪心的鬼畜做法,对拍过了,以为能AC,结果......爆0了，很angry，于是找到了这道题,用yy出来的新算法交了一发居然就A了，跑得还不错?要是手写堆的话可能更快

分析

我先以左端点为第一关键字,右端点为第二关键字排序,然后遍历所有区间\(seg\)

遍历中\(pos\)记录当前满足\(seg[i].l<=pos\)所有区间的最大右端点值,如果新加入的区间左端点大于pos,pos置为\(seg[i].r\),\(cnt\)重置为1

一个小根堆维护刚刚那些\(seg[i].l<=pos\)所有区间的右端点值，如果当前新加入的区间左端点大于堆顶值,弹出堆顶，同时\(cnt-1\)，反复操作直到不满足大于或是堆为空,接着更新答案.

排序\(NlogN\),每个区间最多被弹出一次因此遍历一遍\(NlogN\),因此总时间复杂度\(O(N logN)\)，本来想用Two Pointer但是好像不行

代码

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cctype>

#include <vector>

#include <queue>

#define ll long long

#define ri register int

using std::min;

using std::max;

using std::vector;

using std::priority_queue;

using std::sort;

template <class T>inline void read(T &x){

	x=0;int ne=0;char c;

	while(!isdigit(c=getchar()))ne=c=='-';

	x=c-48;

	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;

	x=ne?-x:x;return ;

}

const int maxn=100005;

const ll inf=1e17;

struct Seg{

	ll l,r;

	bool operator <(const Seg &b)const{

		return l==b.l?r<b.r:l<b.l;

	}

}seg[maxn];

int n;

priority_queue <ll, vector<ll> ,std::greater<ll> >q;

int main(){

	ll x,len,l,r;

	int T;

	read(T);

	while(T--){

		while(q.size())q.pop();

		read(n);

		for(ri i=1;i<=n;i++){

			read(l),read(r);

			seg[i].l=l,seg[i].r=r;

		}

		sort(seg+1,seg+1+n);

		ll pos=-inf;

		int ans=0,cnt=0,lst=0;

		for(ri i=1;i<=n;i++){

			if(seg[i].l>pos){

				while(q.size())q.pop();

				pos=seg[i].r;

				ans=max(ans,cnt);

				cnt=1;

			}

			else cnt++;

			q.push(seg[i].r);

			if(seg[i].r>pos)pos=seg[i].r;

			if(q.size())lst=q.top();

				while(seg[i].l>lst&&q.size()){

				q.pop();cnt--;

					if(!q.empty())lst=q.top();

			}

			ans=max(ans,cnt);

		}

		printf("%d\n",ans);

	}

	return 0;

}

考试看错你会做的题的感觉真....难受

巴特西

HDU5124lines题解-堆+贪心的一个新方法

题目链接

胡扯

分析

代码

最新文章

热门文章