BZOJ1510 POI2006 Kra-The Disks 【模拟】

BZOJ1510 POI2006 Kra-The Disks

还是粘题面吧，但是图就算了

Description

Johnny 在生日时收到了一件特殊的礼物，这件礼物由一个奇形怪状的管子和一些盘子组成. 这个管子是由许多不同直径的圆筒(直径也可以相同) 同轴连接而成. 这个管子的底部是封闭的,顶部是打开的. 下图是由直径为: 5cm, 6cm, 4cm, 3cm, 6cm, 2cm and 3cm 的圆筒组成的管子. 每个圆筒的高度都是相等的, 玩具中所带的盘子也是一些高度和它们相同的圆筒,直径有大有小. Johnny 发明了一种游戏,把盘子从管子顶部一个接一个的扔下去,他想知道最后这些盘子落在了哪,假设盘子落下过程中圆心和管子的轴一直保持一致,比如说我们丢下去三个盘子: 3cm, 2cm and 5cm, 下图展示了最终它们的停止位置: 如图可以知道,盘子掉下去以后,要么被某个圆筒卡住,要么就是因为掉在了以前的一个盘子上而停住. Johnny 想知道他最后扔下去的那个盘子掉在了哪个位置,你来帮他把.

Input

第一行两个整数 n 和 m ( 1<= n, m<= 300 000) 表示水管包含的圆筒数以及盘子总数. 第二行给出 n 个整数 r1, r2,…,rn ( 1 <=ri<= 1 000 000 000 for 1<= i<= n) 表示水管从上到下所有圆筒的直径. 第三行给出m 个整数k1, k2,…, km ( 1<= kj<= 1 000 000 000 for 1<= j<= m) 分别表示Johnny 依次扔下去的盘子直径.

Output

一个整数输出最后一个盘子掉在了哪一层,如果盘子不能扔进水管,那么打印0.

Sample Input

7 3
5 6 4 3 6 2 3
3 2 5

Sample Output

首先直接把能掉到每一层的最大半径处理出来
然后直接倒着模拟回来就行了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define fu(a,b,c) for(int a=b;a<=c;++a)
 4 #define fd(a,b,c) for(int a=b;a>=c;--a)
 5 #define N 300010
 6 int n,m;
 7 int a[N],s[N];
 8 int main(){
 9   scanf("%d%d",&n,&m);
10   fu(i,1,n)scanf("%d",&a[i]);
11   fu(i,1,m)scanf("%d",&s[i]);
12   fu(i,2,n)a[i]=min(a[i],a[i-1]);
13   int p=n;
14   fu(i,1,m){
15     while(p&&a[p]<s[i])p--;
16     if(p&&i!=m)p--;
17   }
18   printf("%d",p);
19   return 0;
20 }