题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1510
题意：一根水管，不同段的粗细不同，向下丢圆盘，会在细的地方被卡住... 求最后一个圆盘停留的位置
由于细水管下面的粗水管是没有意义的，所以可以对原序列求一个前缀 min，然后就原序列就单调啦，可以二分了... 又刷水题啦...
有点细节比较讨厌...WA 了几次
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 300010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,a[N],tmp,ans; int main() { n=read(),m=read(); a[1]=read(); for(int i=2;i<=n;i++) {a[i]=read();if(a[i]>a[i-1])a[i]=a[i-1];} ans=n+1; for(int i=1;i<=m;i++) { tmp=read(); int l=1,r=ans-1,la=r; while(l<=r) { int mid=(l+r)>>1; if(a[mid]<tmp)la=mid,r=mid-1; else l=mid+1; } ans=la; if(a[la]<tmp)ans--; } printf("%d",ans); } |
Comments | NOTHING