# 11557: 【原1557】奶牛计数

### 题目描述

author: Zhiyin Chen 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1557

## Description

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.

## Input Format

• Line 1: Two integers, N and D.
• Lines 2..1+N: Line i+1 contains the integers x(i) and h(i). The locations of all N cows are distinct.

## Output Format

• Line 1: The number of crowded cows.

## Sample Input

``````6 4
10 3
6 2
5 3
9 7
3 6
11 2
``````

## Sample Output

``````2
``````

## Sample Explanation

There are 6 cows, with a distance threshold of 4 for feeling crowded. Cow #1 lives at position x=10 and has height h=3, and so on.

The cows at positions x=5 and x=6 are both crowded.

## WashSwang's solution

``````#include <iostream>
#include <cstdio>
void qsort(int *s,int *t,int *p,int *q){
if (t-s<=1) return;
int i=0,j=int(t-s)-1,x=s[0],y=p[0];
while (i<j){
while (i<j&&s[j]>=x) j--;
if (i<j) {s[i]=s[j]; p[i++]=p[j];}
while (i<j&&s[i]<=x) i++;
if (i<j) {s[j]=s[i]; p[j--]=p[i];}
}
s[j]=x;
p[j]=y;
qsort(s,s+j,p,p+j);
qsort(s+j+1,t,p+j+1,q);
}
int main() {
scanf("%d%d",&n,&d);
for (int i=0;i<n;++i) scanf("%d%d",&x[i],&h[i]);
qsort(x,x+n,h,h+n);
tail=0;
for (;x[p]<=d&&p<n;++p){
lmax[p]=h[a[tail]];
}
for (;p<n;++p){
lmax[p]=h[a[tail]];
}
tail=0;
for (p=n-1;x[p]>=x[n-1]-d;--p){
rmax[p]=h[a[tail]];
}
for (;p>=0;--p){
rmax[p]=h[a[tail]];
}
for (int i=0;i<n;++i)
if (2 * h[i] <= lmax[i] && 2 * h[i] <= rmax[i]) ans++;
printf("%d",ans);
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 50000;
struct cow {
int x, h;
} c[MAX_N + 5];

bool leftCrowded[MAX_N + 5], rightCrowded[MAX_N + 5];
int q[MAX_N + 5];
int head, tail, ans, n, d;

bool cmp(const cow & c1, const cow & c2) {
return c1.x < c2.x;
}

int main() {

ios::sync_with_stdio(false);

cin >> n >> d;
for (int i = 0; i < n; ++i) cin >> c[i].x >> c[i].h;

sort(c, c + n, cmp);// make x in ascending order
for (int i = 1; i < n; ++i) {
int nearestPos = c[i].x - d;
while (head <= tail && c[q[tail]].h <= c[i].h) tail--;
if (c[q[head]].h >= c[i].h << 1) leftCrowded[i] = true;
q[++tail] = i;
}

q[0] = n - 1;
for (int i = n - 2; i >= 0; --i) {
int nearestPos = c[i].x + d;