E. Pillars（Codeforces Round #271) - c++编程基础

TOP

E. Pillars（Codeforces Round #271)

2015-07-20 17:31:02 来源: 作者: 【大中小】浏览:2次

E. Pillars time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Marmot found a row with n pillars. The i-th pillar has the height of hi meters. Starting from one pillar i1, Marmot wants to jump on the pillarsi2, ..., ik. (1?≤?i1? i2? ik?≤?n). From a pillar i Marmot can jump on a pillar j only if i? j and |hi?-?hj|?≥?d, where |x| is the absolute value of the number x.

Now Marmot is asking you find out a jump sequence with maximal length and print it.

Input

The first line contains two integers n and d (1?≤?n?≤?105, 0?≤?d?≤?109).

The second line contains n numbers h1,?h2,?...,?hn (1?≤?hi?≤?1015).

Output

The first line should contain one integer k, the maximal length of a jump sequence.

The second line should contain k integers i1,?i2,?...,?ik (1?≤?i1? i2? ik?≤?n), representing the pillars' indices from the maximal length jump sequence.

If there is more than one maximal length jump sequence, print any.

Sample test(s) input

5 2
1 3 6 7 4

output

4
1 2 3 5

input

10 3
2 1 3 6 9 11 7 3 20 18

output

6
1 4 6 7 8 9

Note

In the first example Marmot chooses the pillars 1, 2, 3, 5 with the heights 1, 3, 6, 4. Another jump sequence of length 4 is 1, 2, 4, 5.

因为一个字母写错，纠结了几天

首先将高度排序离散化，以离散化后的元素个数N为下标建立线段树，线段树每个下标表示一个高度，对于所有下标i 然后我们从左到右处理每个点（未离散化之前的点），对于第i个点，设其高度为num[i]，则我们在高度1~num[i]-K(即线段树的(1，Lfind(num[i])内找到一个最长长度，在num[i]+K~N,即线段树的(Rfind(num[i],cur)内找到一个最长长度，取最优的一个，长度+1用以更新当前点，同时记录前驱。最后再递归输出就行了。

代码：

//156ms #include #include #include #include #include using namespace std; const int maxn=1e5+10; int pre[maxn];//记录前一个点 long long num[maxn]; long long a[maxn]; int cur; struct node { int maxcou;//以这个高度结尾的最大长度 int pos;//以这个高度结尾的元素的位置 }tree[maxn<<2]; void build(int rt,int l,int r) { if(l==r) { tree[rt].maxcou=0; tree[rt].pos=0; return; } int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); tree[rt].maxcou=0; tree[rt].pos=0; } int Rfind ( long long x ) { int l = 1 , r = cur ; while ( l < r ) { int m = ( l + r ) / 2 ; if ( a[m] >= x ) r = m ; else l = m + 1 ; } return l ; } int Lfind ( long long x ) { int l = 1 , r = cur ; while ( l < r ) { int m = ( l + r + 1 ) / 2 ; if ( a[m] <= x ) l = m ; else r = m - 1 ; } return r ; } void update(int x,int v,int i,int rt,int l,int r) { if(l==r) { if(v>tree[rt].maxcou) { tree[rt].maxcou=v; tree[rt].pos=i; } return; } int mid=(l+r)>>1; if(x<=mid) update(x,v,i,rt<<1,l,mid); else update(x,v,i,rt<<1|1,mid+1,r); if(tree[rt<<1].maxcou>tree[rt<<1|1].maxcou) { tree[rt].maxcou=tree[rt<<1].maxcou; tree[rt].pos=tree[rt<<1].pos; } else { tree[rt].maxcou=tree[rt<<1|1].maxcou; tree[rt].pos=tree[rt<<1|1].pos; } } int maxcount,maxpos; void query(int L,int R,int rt,int l,int r) { if(L>R) return; if(L<=l&&R>=r) { if(tree[rt].maxcou>maxcount) { maxcount=tree[rt].maxcou; maxpos=tree[rt].pos; } return; } int mid=(l+r)>>1; if(L<=mid) query(L,R,rt<<1,l,mid); if(R>mid) query(L,R,rt<<1|1,mid+1,r); } void prin(int u) { if(pre[u]!=0) { prin(pre[u]); printf("%d ",pre[u]); } return; } int main() { int n,k,ids=1,ans=1; scanf("%d%d",&n,&k); memset(pre,0,sizeof(pre)); for(int i=1;i<=n;i++) { scanf("%I64d",&num[i]); a[i]=num[i]; } sort(a+1,a+n+1); cur=1; for(int i=2;i<=n;i++)//离散化，以元素的个数来建树，每个叶子节点代表一个高度 if(a[i]!=a[cur]) { a[++cur]=a[i]; } build(1,1,cur); update(Lfind(num[1]),1,1,1,1,cur); pre[1]=0; for(int i=2;i<=n;i++) { int L=Lfind(num[i]-k);//小于num[i]-k的最大位置 int R=Rfind(num[i]+k);//大于num[i]+k的最小位置 maxcount=0,maxpos=0; if(a[L]+k<=num[i]) { query(1,L,1,1,cur); } if(num[i]+k<=a[R]) { query(R,cur,1,1,cur); } update(Lfind(num[i]),maxcount+1,i,1,1,cur); pre[i]=maxpos; if(maxcount+1>ans) { ans=maxcount+1; ids=i; } } printf("%d\n",ans); prin(ids); printf("%d\n",ids); return 0; }

在CF看到的一个投机取巧的方法，数据也很难出到这么强，在比赛的时候可以水一发。

#include #include #include #include #include #include const int maxn=100000+100; using namespace std; int main() { int n, d; scanf("%d%d",&n,&d); long long h[maxn]; int z[maxn],p[maxn]; for(int i=0; i =d && z[j]+1>z[i]){ z[i]=z[j]+1; p[i]=j; } } } int max=-100,index; for(int i=0; i max) { max=z[i]; index=i; } } printf("%d\n",max); vector a; a.push_back(index); max--; while(max>0){ index=p[index]; a.push_back(index); max--; } for(int i=a.size()-1; i>=0; i--) { printf("%d ",a[i]+1); } }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：ZOJ2587 Unique Attack	下一篇：hdu 3076 ssworld VS DDD (概率dp)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: