自动搬运

查看原文

来自洛谷，原作者为

	Azazеl Just the smallest grain in the sands

搬运于2025-08-24 22:21:34，当前版本为作者最后更新于2021-06-24 21:47:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

$~~~~$ 给出 $n$ 个数表示砖长，通过排列使其构成一个数列，满足 $a_i+D\geq a_{i+1}$，求可以构成的数列个数（每个数字互不相同）

题解

$~~~~$ 显然某一块砖能放在哪些砖上面是固定的，并且在升序的序列中，对于砖块 $i$ ，它可以放的砖块区间是一个右端 $r=n$，左端点 $l\leq i$ 的区间。

$~~~~$ 因此先升序排序，从左至右对每一块砖维护其能放在哪些前面的砖上面。

$~~~~$ 注意到必须满足 $a_i+d\geq a_j(i<j)$，因此在升序的 $a$ 序列里随着 $j$ 的增加，最小的满足条件的 $i$ 也会增加。

$~~~~$ 因此对于每个砖块 $i$ 双指针维护合法区间 $[l,r]$（这里的 $r=i$ ），注意到放在地上/更大的砖上也是一种选择（但是放在哪块最大的砖上是由大砖来计算的），因此每块砖的合法数量为 $r-l+1$，累乘即可。

代码

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
int arr[620005];
const int MOD=1e9+9;
int main() {
	int n,k;ll Ans=1;
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
	sort(arr+1,arr+1+n);
	for(int l=1,r=1;r<=n;r++)
	{
		while(arr[l]+k<arr[r]) l++;
		Ans=Ans*(r-l+1)%MOD;
	}
	printf("%lld",Ans);
	return 0;
}