前言

在我和好友 UCPP 的热血沸腾的组合技之后，这道题所有题解都被我们叉了，所以抓紧补一篇题解。

题解

先来想暴力做法，再考虑如何优化。

暴力做法非常简单，枚举每一对奶牛（记作奶牛

i

和奶牛

j

），只要比较这两头奶牛的距离

\left | p_i-p_j \right |

和

d

的大小即可。时间复杂度

O(n^2)

，显然超时。

考虑优化。我们发现，在我们对

p

数组排序后，对于每头奶牛（记作奶牛

i

），它后面的所有奶牛离它的距离

p_j-p_i(i<j \le n)

肯定是逐渐增加的。换而言之，对于每头奶牛

i

，我们只要找出满足

i <j \le n

且

p_j-p_i\le d

的

j

的数量即可。答案具有单调性，考虑二分。

手写二分太过麻烦。在 C++ 的 STL 中，有一个很好用的函数：upper_bound。它可以找出在一个有序的数组中大于给定值的第一个元素。举个例子，在数组

a=\{1,1,4,5,14\}

中想要查找第一个大于

4

的数，代码可以写为 int id=upper_bound(a,a+5,4)-a;。其中 id 的值就是

5

的下标，也就是

3

。

以上算法的时间复杂度为

O(n \log n)

，瓶颈在排序和二分部分。

本题还有一个坑：如果数据到达极限，共

10^6

头奶牛，相邻两头奶牛的

p

值也是相邻的，这样答案大约是

10^{10}

，int 会爆。

学会了这些，代码就能轻松写出了。

代码

CPP

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,d;
int a[1000005];
ll ans=0;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		int x=upper_bound(a+i+1,a+n+1,a[i]+d)-a;
		ans+=x-i-1;
	}
	cout<<ans<<endl;
	return 0;
}
/*
---INFORMATIONS---
TIME:2025-05-14 13:02:02
PROBLEM:P1296
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

题解：P1296 奶牛的耳语

文章操作

前言

题解

代码

相关推荐

评论

题解：P1296 奶牛的耳语