Rockdu's Blog

【题目描述】

农夫约翰的N头奶牛(3 ≤ N ≤ 1000)站在一排，每一处有明显的位置线。他们正在练习投掷棒球，准备对邻近的农场奶牛一场重要的比赛。

农民约翰，他观察一组三头奶牛（x，y，z）完成两个成功的投球。牛X向右投球给牛Y，然后牛Y把球向右抛给牛Z。农民约翰指出：第二投，是第一投的一到二倍远。请计算牛可能的三元组的数目。

(Cow X throws the ball to cow Y on her right, and then cow Y throws the ball to cow Z on her right.)

【输入】

第1行：牛的数量，N。

第2..1+N行：每行包含一个整数牛位置（范围在0..100000000的整数）。

【输出】

一行，三元组的奶牛数量（X，Y，Z），其中Y在X右边，Z在Y右边，从Y到Z之间的距离为|XY|--2|XY|（含），|XY|是X到Y的距离。

【输入样例】

5
3
1
10
7
4

【输出样例】

4

【提示】

输入详细信息：

有5头奶牛，在位置3，1，10，7，和4。

输出的细节：

四个可能的三元组是奶牛的位置1-3-7，1-4-7，4-7-10，和1-4-10。

这个题其实比较一眼，只要对所有的牛先按位置排序，O(n^2)枚举其中两头牛，向右二分查找出最小的不低于一倍的牛和最小的高于两倍的牛前后减一减，把每次枚举的答案累加即可。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e3 + 5;
int cows[maxn], n, l, r, ans;
int main() {
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &cows[i]);
	sort(cows + 1, cows + n + 1);
	for(register int i = 1; i < n; ++i)
		for(register int j = i + 1; j <= n; ++j) {
			l = lower_bound(cows + 1, cows + n + 1, cows[j] + (cows[j] - cows[i])) - cows;
			r = upper_bound(cows + 1, cows + n + 1, cows[j] + (cows[j] - cows[i]) * 2) - cows;
			if(l > n) continue;
			ans += (r - l);
		}
	printf("%d", ans);
	return 0;
}