题目描述

Farmer John's N cows (1 <= N <= 50,000) are grazing along a one-dimensional fence. Cow i is standing at location x(i) and has height h(i) (1 <= x(i),h(i) <= 1,000,000,000).

A cow feels "crowded" if there is another cow at least twice her height within distance D on her left, and also another cow at least twice her height within distance D on her right (1 <= D <= 1,000,000,000). Since crowded cows produce less milk, Farmer John would like to count the number of such cows. Please help him.

FJ有N(1 <= N <= 50,000)头奶牛沿着一维的栅栏吃草，第i头奶牛在目标点x(i) ，它的身高是 h(i) (1 <=x(i),h(i) <= 1,000,000,000)。

当一头奶牛左边D距离内而且右边D距离内有身高至少是它的两倍的奶牛，t (1 <= D <= 1,000,000,000)，它就会觉得拥挤。

请计算觉得拥挤的奶牛的数量。

原题链接

Solve

手动模拟一下队列就行。

1.一个递减的单调队列，保证队首是最近最高的“奶牛”（最高优先）

2.依次遍历，如果队首的比他高两倍以上，就把他标记下来；否则就不标。

3.从左到右，从右到左，重复两次，有两次标记的就是“Crowded Cows"。

Tips：

为什么如此标记呢？

首先，我们保证了队首是最近最高的“奶牛”。所以如果队首都没有他高，那就没有比他高的的了（最起码他前面没有了）。而第二次遍历就是解决他后面是否有比他高的“奶牛”（上文的“高”都是指高出两倍及以上）。

具体见代码

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;  //标准开头
const int N=500001;
int n,m;  //n==n,m==d
int q[N][3];  //核心队列
struct note{
	int x,h,r;
}d[N];  //d存储每头“奶牛”的信息——位置（x），高度（h)，序号(r)（序号可以方便标记）
bool vis[N][3];  //标记小能手
int ans;   //答案
int head=1,tail=1;  //head——队首，tail——队尾
bool cmp(const note &a,const note &b){  //按位置从小到大排
	return a.x<b.x;
}
int main()
{
	memset(q,0,sizeof(q));
	memset(vis,false,sizeof(vis));
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>d[i].x>>d[i].h,d[i].r=i;
	sort(d+1,d+1+n,cmp);  //sort快排，其实也可以换成其他的方法，只要不影响结果
	q[head][0]=d[1].r;
	q[head][1]=d[1].x;
	q[head][2]=d[1].h;
	for(int i=2;i<=n;i++){
		while(q[head][1]<d[i].x-m&&head<=tail) head++;  //如果队首的位置已经超出了当前“奶牛”的范围，那么队首就没有“利用价值”了，甚至会影响正常标记，所以必须删去（其实删去不是真正的删去，只是头指针后移）。
		if(q[head][2]>=d[i].h*2) vis[d[i].r][1]=true;  //标记
		while(q[tail][2]<d[i].h&&tail>=head) tail--;  //队列更新
		tail++;
		q[tail][0]=d[i].r;
		q[tail][1]=d[i].x;
		q[tail][2]=d[i].h;
	}
	head=1;
	tail=1;
	memset(q,0,sizeof(q));
	q[head][0]=d[n].r;
	q[head][1]=d[n].x;
	q[head][2]=d[n].h;
	for(int i=n-1;i>=1;i--){  //再来一遍
		while(q[head][1]>d[i].x+m&&head<=tail) head++;
		if(q[head][2]>=d[i].h*2) vis[d[i].r][2]=true;
		while(q[tail][2]<d[i].h&&tail>=head) tail--;
		tail++;
		q[tail][0]=d[i].r;
		q[tail][1]=d[i].x;
		q[tail][2]=d[i].h;
	}
	for(int i=1;i<=n;i++){  //注意是两次标记都有，才是“Crowded Cows”
		if(vis[i][1]==true&&vis[i][2]==true) ans++;
	}
	cout<<ans;  //完美输出
	return 0;
}