「CEOI2010 day2」 Tower 题解

题意

\(~~~~\) 给出 \(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;
}
上一篇:POJ1958 Strange Tower of Hanoi(4塔汉诺塔)


下一篇:强大的Git客户端:Tower for Mac(v7.0(290)破解版)