首页 > 代码库 > 51nod 扔盘子
51nod 扔盘子
题目传送门
这道题一开始写了n方的算法 果不其然 它T了
所以就想想o(n)的算法 写不出来 就像sbzhq学习了一下
这道题啊 要维护一下从深度1到n每一段的最小值以及他的位置 然后就暴力搞一搞就okay 啦!!!
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int inf=1e9+7; int read(){ int ans=0,f=1,c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+(c-‘0‘); c=getchar();} return ans*f; } int n,m,head=1,top,ans; int s[50007],a[50007],sum[50007],mn[50007]; int main(){ n=read(); m=read(); top=n; sum[0]=inf; mn[0]=0; for(int i=1;i<=n;i++){ s[i]=read(); sum[i]=sum[i-1]; mn[i]=mn[i-1]; if(s[i]<=sum[i]) sum[i]=s[i],mn[i]=i; } for(int i=1;i<=m;i++) a[i]=read(); while(top&&head<=m){ if(sum[top]>=a[head]) ans++,head++,top--; else top=mn[top]-1; } printf("%d\n",ans); return 0; }
51nod 扔盘子
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。