13860. Crowded CowsConstraints
Time Limit: 1 secs, Memory Limit: 256 MB
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
* 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
* Line 1: The number of crowded cows.
Sample Input6 410 36 25 39 73 611 2Sample Output2Hint
In the sample, 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.
Problem Source
2015年每周一赛第二场
按x从小到大排序，而后从左往右扫，维护一个x递增，h递减的双头队列。
对于新的牛，从队列左侧开始，弹出位置超过限制的牛，这些牛必然比新牛及后来的牛位置更远，从队列右侧开始，弹出高度没有新牛高的牛，因为这些牛比新牛矮而且位置也
更远，，都是必然没有新牛有可能符合“拥挤”的牛。
这是确定左边拥挤，同理确定右边拥挤即可。
#include <iostream>#include <algorithm>using namespace std;struct cow {int x, h;}c[50005];bool isLeftCrowded[50005];bool cmp(const cow & c1, const cow & c2) {return c1.x < c2.x;}int main() {std::ios::sync_with_stdio(false);int n, d;cin >> n >> d;for (int i = 0; i < n; i++) cin >> c[i].x >> c[i].h;sort(c, c + n, cmp);int q[50005];int head, tail, ans = 0;head = tail = 0;q[0] = 0;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) isLeftCrowded[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 && isLeftCrowded[i]) ans++;q[++tail] = i;}cout << ans << endl;return 0;}
伟人所达到并保持着的高处，并不是一飞就到的，
