有N(2<=N<=620000)快砖，要搭一个N层的塔，要求：如果砖A恰好在砖B上面，那么A不能比B的长度+D要长。问有几种方法,输出 答案 mod 1000000009的值
没想出来 菜鸡.jpg 考虑按照砖的长度从短到长依次加入. 对于一个合法的塔,我们抽掉其中最长的一块砖,剩下的砖按照原先的顺序必然还是合法的塔.
假如最长的砖在最下方,那么显然不会从合法变成不合法. 假如不在最下方,设最长的砖长度为x,它下方的砖长度为a,上方的砖长度为b. 那么a+d>=x.抽掉x之后,因为x>=b,所以必然a+d>=b
那么我们现在在一个合法的塔中插入一个比现在所有砖都长的砖.因为比现在的所有砖都长,这块新加进来的砖一定不会和它上方的砖产生矛盾.只需要考虑哪些位置不会和它下方的砖产生矛盾即可.也就是找出有多少块砖长度>=新加的砖的长度-d.注意新加的砖还可以在整个塔最下方,这一步的方案数是"长度>=新加的砖的长度-d"的砖的块数+1. 每一步的方案数乘起来即可.
#include<cstdio> #include<algorithm> using namespace std; const int maxn=700005; const int mod=1000000009; int a[maxn]; int main(){ int n,d;scanf("%d%d",&n,&d); for(int i=1;i<=n;++i)scanf("%d",a+i); sort(a+1,a+n+1); int ans=1; int pt=1; for(int i=1;i<=n;++i){ while(pt<=n&&a[pt]<a[i]-d)++pt; ans=ans*1ll*(i-pt+1)%mod; } printf("%d\n",ans); return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7009158.html
相关资源：数据结构—成绩单生成器