关于第二问的贪心
查看原帖
关于第二问的贪心
790274
InQueue楼主2024/10/27 12:57

rt,已知 segv 已经将包含了其他区间的区间去掉,并升序排好序,求下面这么做的反例。

queue<ll> q;
ll ans = 0;
for(Seg i : segv)
{
	while(q.size() && p[q.front()] < i.l)
	{
		q.pop();
	}
	if(!q.size())
	{
		ans++;
		for(ll j=pre[i.l];j<=m&&p[j]<=i.r;j++)
		{
			if(p[j] >= i.l)
			{
				q.push(j);
			}
		}
	}
}
cout << m - ans << endl;
2024/10/27 12:57
加载中...