51nod 扔盘子
2024-08-28 08:29:22
这道题一开始写了n方的算法 果不其然 它T了
所以就想想o(n)的算法 写不出来 就像sbzhq学习了一下
这道题啊 要维护一下从深度1到n每一段的最小值以及他的位置 然后就暴力搞一搞就okay 啦!!!
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=1e9+;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,m,head=,top,ans;
int s[],a[],sum[],mn[];
int main(){
n=read(); m=read(); top=n;
sum[]=inf; mn[]=;
for(int i=;i<=n;i++){
s[i]=read();
sum[i]=sum[i-]; mn[i]=mn[i-];
if(s[i]<=sum[i]) sum[i]=s[i],mn[i]=i;
}
for(int i=;i<=m;i++) a[i]=read();
while(top&&head<=m){
if(sum[top]>=a[head]) ans++,head++,top--;
else top=mn[top]-;
}
printf("%d\n",ans);
return ;
}
最新文章
- CentOS6.5 安装 jdk1.7
- go 的 time ticker 设置定时器
- 【概念笔记】JAVA基础 - part2
- 【转】KM匹配题集
- AsyncEnumerableExtensions.cs z
- (四)JAVA使用POI操作excel
- js随机模块颜色
- 实践作业1:测试管理工具实践 Day3
- 【bzoj1045】【HAOI2008】 糖果传递
- LeetCode算法题-Relative Ranks(Java实现)
- ARIMA模型识别、计算p、q值
- Java知多少(65)线程的挂起、恢复和终止
- mysql导入导出表
- C# NPOI使用
- 【MongoDB-query查询条件】
- 跟我学AngularJS:全局变量设置之value vs constant vs rootscope vs 服务[转]
- 在ubuntu下安装使用latex
- LR下载及破解
- systemtap 用户态调试3
- csharp:qq weather