专栏文章

题解：P1296 奶牛的耳语

___CrossBow_EXE__
P1296题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipai30o
此快照首次捕获于
2025/12/03 08:49
3 个月前
此快照最后确认于
2025/12/03 08:49
3 个月前
查看原文

前言

这题自从被我 hack 之后已经过去 3 天了，居然还能交题解，再补一个分块做法。

题解

序列是无序的，先排个序。排完序后，把序列分成 n\sqrt n 块，每一块都找出一个最大值。因为序列有序，所以最大值肯定是这一块的最后一个数。
如果我们使用暴力做法，我们需要统计每头奶牛后面有多少奶牛与这头奶牛距离小于等于 dd，很慢。我们可以枚举每块，如果这一块的最大值都比 dd 小或相等，那这一块的其他数就更不用说了。复杂度来到了 O(nn)O(n \sqrt n)。
下面是这种思路的代码：
CPP
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,d;
const int N=1000005;
int a[N],len;
int id[N],maxn[N];
int l[N],r[N];//每块的左右端点 
int lst;//最后一块的编号 
ll ans=0;
signed main(int argc,char *argv[]){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(NULL);
	cin.tie(0),cout.tie(0);
	cin>>n>>d;
	len=sqrt(n);//块长 
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);//排序 
	for(int i=1;i<=n;i++){
		id[i]=i/len+1;//块编号
		lst=id[i];
		if(id[i]!=id[i-1]){//新的一块 
			l[id[i]]=i;//这一块的左端点为当前点 
			r[id[i]-1]=i-1;//上一块的右端点为上一个点 
			maxn[id[i]-1]=a[i-1];//上一块的最大值为上一个数字 
		}
	}
	r[lst]=n;
	maxn[lst]=a[n];
	for(int i=1,t;i<=n;i++){
		bool flag=0;
		for(int j=i+1;j<=r[id[i]];j++){//遍历这一块其他元素 
			if(a[i]+d>=a[j]) ans++;
			else{
				flag=1;//找到比它大的了
				break; 
			}
		}
		if(flag) continue;
		for(int j=id[i]+1;j<=lst;j++){//遍历后面所有块 
			if(maxn[j]<=a[i]+d) ans+=r[j]-l[j]+1;//加上这一块的大小
			else{
				//这一块有比它大的
				for(int k=l[j];k<=r[j];k++){
					if(a[k]<=a[i]+d) ans++;
					else break;
				}
				break;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
---INFORMATIONS---
TIME:2025/5/16 9:22:10
PROBLEM:P1296
CODE BY __CrossBow_EXE__ Luogu uid967841
*/
还能小优化一下：把 O(n)O(\sqrt n) 枚举块的过程转化为 O(log⁡n)O(\log n) 的二分。（但怎么更慢了……）
CPP
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,d;
const int N=1000005;
int a[N],len;
int id[N],maxn[N];
int l[N],r[N];//每块的左右端点 
int lst;//最后一块的编号 
ll ans=0;
bool check(int i,int x){
	if(maxn[x]<=a[i]+d) return 1;
	else return 0;
}
signed main(int argc,char *argv[]){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(NULL);
	cin.tie(0),cout.tie(0);
	cin>>n>>d;
	len=sqrt(n);//块长 
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);//排序 
	for(int i=1;i<=n;i++){
		id[i]=i/len+1;//块编号
		lst=id[i];
		if(id[i]!=id[i-1]){//新的一块 
			l[id[i]]=i;//这一块的左端点为当前点 
			r[id[i]-1]=i-1;//上一块的右端点为上一个点 
			maxn[id[i]-1]=a[i-1];//上一块的最大值为上一个数字 
		}
	}
	maxn[lst+1]=2147483647;
	l[lst+1]=n+1;
	r[lst]=n;
	maxn[lst]=a[n];
	for(int i=1;i<=n;i++){
		bool flag=0;
		for(int j=i+1;j<=r[id[i]];j++){//遍历这一块其他元素 
			if(a[i]+d>=a[j]) ans++;
			else{
				flag=1;//找到比它大的了
				break; 
			}
		}
		if(flag) continue;
		//二分，启动！！！ 
		int lt=id[i]+1,rt=lst;
		while(lt<=rt){
			int mid=(lt+rt)>>1;
			if(check(i,mid)) lt=mid+1;
			else rt=mid-1;
		}
		ans+=l[lt]-r[id[i]]-1;
		for(int j=l[lt];j<=r[lt];j++){
			if(a[j]<=a[i]+d) ans++;
			else break;
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
---INFORMATIONS---
TIME:2025/5/16 9:22:10
PROBLEM:P1296
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

后记

本蒟蒻的第 2626 篇题解，也是我第一次一道题交两篇题解。
自己 hack 的题写题解就是爽！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...