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

Sample Output

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 ans,p,x[100000],n,d,head,tail,h[100000],a[100000],lmax[100000],rmax[100000],bx[100000];
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);
    head=0;
    tail=0;
    for (;x[p]<=d&&p<n;++p){
        while (head>0&&h[a[head-1]]<=h[p]) head--;
        a[head++]=p;
        lmax[p]=h[a[tail]];
    }
    for (;p<n;++p){
        while (tail<head&&x[a[tail]]+d<x[p]) tail++;
        while (head>tail&&h[a[head-1]]<=h[p]) head--;
        a[head++]=p;
        lmax[p]=h[a[tail]];
    }
    head=0;
    tail=0;
    for (p=n-1;x[p]>=x[n-1]-d;--p){
        while (head>0&&h[a[head-1]]<=h[p]) head--;
        a[head++]=p;
        rmax[p]=h[a[tail]];
    }
    for (;p>=0;--p){
        while (tail<head&&x[a[tail]]-d>x[p]) tail++;
        while (head>tail&&h[a[head-1]]<=h[p]) head--;
        a[head++]=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[head]].x < nearestPos) head++;
        while (head <= tail && c[q[tail]].h <= c[i].h) tail--;
        if (head > tail) q[head] = i;
        if (c[q[head]].h >= c[i].h << 1) leftCrowded[i] = true;
        q[++tail] = i;
    }

    head = tail = 0;
    q[0] = n - 1;
    for (int i = n - 2; i >= 0; --i) {
        int nearestPos = c[i].x + d;
        while (head <= tail && c[q[head]].x > nearestPos) head++;
        while (head <= tail && c[q[tail]].h <= c[i].h) tail--;
        if (head > tail) q[head] = i;
        if (c[q[head]].h >= c[i].h << 1) rightCrowded[i] = true;
        q[++tail] = i;
    }

    for (int i = 0; i < n; ++i)
        ans += leftCrowded[i] && rightCrowded[i];
    cout << ans << endl;

    return 0;
}