好贷网好贷款

SGU 458 The Monochrome Picture解题报告

发布时间:2016-12-4 12:00:25 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"SGU 458 The Monochrome Picture解题报告",主要涉及到SGU 458 The Monochrome Picture解题报告方面的内容,对于SGU 458 The Monochrome Picture解题报告感兴趣的同学可以参考一下。

题目大意:转化题意后,即给你长度为10^5个整数,大小为1-10^6,问最少去掉几个数,使相邻的两个数的大小差不为1 解题思路:本题可以用线段树解决,建立一颗大小为10^6的线段树,对于a[i],查询1~a[i]-2,a[i],a[i]+2~10^6,三段的最大值,以a[i]结尾的最大值就是该值加1,在将值插入线段树,更新,最后求答案及时从末尾在便利一边。 通过代码: #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <vector> #include <map> #include <queue> #include <set> using namespace std; const int maxint = -1u>>1; #define N 100010 #define M 1000000 int num[M*4+10]; int f[N],a[N]; int ans[N]; void build(int t, int l, int r) { num[t] = 0; if (l==r) return; int mid =(l+r)/2; build(2*t,l,mid); build(2*t+1,mid+1,r); } int search(int t,int l,int r,int tl,int tr) { if (l>tr||tl>r) return 0; if (l>=tl&&tr>=r) return num[t]; int mid=(l+r)/2; int ans1=search(2*t,l,mid,tl,tr); int ans2=search(2*t+1,mid+1,r,tl,tr); return max(ans1,ans2); } void insert(int t,int l,int r,int pos,int val) { if (l>pos||r<pos) return; if (l==r) num[t]=max(num[t],val); else{ int mid =(l+r)/2; insert(2*t,l,mid,pos,val); insert(2*t+1,mid+1,r,pos,val); num[t]=max(num[t],max(num[2*t],num[2*t+1])); } } int main() { int n; while (scanf("%d", &n)==1) { for (int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,0,M); for (int i=1;i<=n;i++){ int t1=search(1,0,M,0,a[i]-2); int t2=search(1,0,M,a[i],a[i]); int t3=search(1,0,M,a[i]+2,M); f[i]=max(t1,max(t2,t3))+1; insert(1,0,M,a[i],f[i]); } int id=n; for (int i=n-1;i>0;i--) if (f[i]>f[id]) id=i; printf("%d\n",n-f[id]); int tot=0; while (id > 0) { ans[++tot]=a[id]; int tp=id; while (id>=0&&(abs(a[tp]-a[id])==1||f[tp]!=f[id]+1)) id--; } for (int i=tot;i>=1;i--) if (i>1) printf("%d ",ans[i]); else printf("%d\n",ans[i]); } return 0; }

上一篇:谷歌三大核心技术
下一篇:linux 高级删除命令 ----- 按时间删除

相关文章

相关评论