FJ的N头牛正沿着一个笔直的围栏放牧。奶牛i站在位置X_iX i 上,其高度为H_iH i 。奶牛感觉“拥挤”,是在一头牛的左边D距离内(包括边界D)至少有她两倍的高度的牛存在,还有她右边D距离内(包括边界D)至少有她两倍的高度的牛存在,所以这头牛就感觉到了“拥挤”。由于拥挤的奶牛产奶量少,农民约翰想减少拥挤的奶牛数量。请帮助他。 Input 第1行:两个用空格隔开的整数,N和D,意义如题目描述; 第2到N+1行:第i+1行第i头奶牛的信息,包含两个整数X_iX i 和H_iH i ,N头奶牛的位置互不相同。
时间: 2024-04-19 18:23:32 浏览: 111
你可以使用以下的C++代码来解决这个问题:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
struct Cow {
int position;
int height;
};
bool isCowCrowded(const Cow& cow, const std::vector<Cow>& cows, int distance) {
int leftCount = 0;
int rightCount = 0;
int leftBoundary = cow.position - distance;
int rightBoundary = cow.position + distance;
for (const Cow& otherCow : cows) {
if (otherCow.position >= leftBoundary && otherCow.position <= cow.position && otherCow.height >= 2 * cow.height) {
leftCount++;
}
if (otherCow.position <= rightBoundary && otherCow.position >= cow.position && otherCow.height >= 2 * cow.height) {
rightCount++;
}
}
return leftCount >= 2 && rightCount >= 2;
}
int main() {
int N, D;
std::cin >> N >> D;
std::vector<Cow> cows(N);
for (int i = 0; i < N; i++) {
std::cin >> cows[i].position >> cows[i].height;
}
int crowdedCount = 0;
for (const Cow& cow : cows) {
if (isCowCrowded(cow, cows, D)) {
crowdedCount++;
}
}
std::cout << crowdedCount << std::endl;
return 0;
}
```
这段代码首先定义了一个 `Cow` 结构体,用来表示每头奶牛的位置和高度。然后,通过 `isCowCrowded` 函数判断一头奶牛是否感觉到拥挤,该函数会检查该奶牛的左边和右边是否有至少两头高度是她两倍的奶牛。
在 `main` 函数中,首先读取输入的 N 和 D,然后读取每头奶牛的位置和高度。接下来,使用一个循环遍历每头奶牛,调用 `isCowCrowded` 函数判断是否感觉到拥挤,并统计感觉到拥挤的奶牛数量。最后,输出拥挤的奶牛数量。
希望这个代码能够帮助你解决问题!如果还有其他问题,请随时提问。
阅读全文