首页 > 代码库 > BZOJ1510: [POI2006]Kra-The Disks
BZOJ1510: [POI2006]Kra-The Disks
1510: [POI2006]Kra-The Disks
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 265 Solved: 157
[Submit][Status]
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
5 6 4 3 6 2 3
3 2 5
Sample Output
2
HINT
Source
题解:
总算碰到了一道水题。。。
考虑到如果下一个圆柱比上一个圆柱面积大,那么它的有效面积也只能是上一个圆柱的面积,所以不妨就把它的面积记为上一个圆柱的面积。
然后我们得到了一个单调下降的面积序列。
然后我们模拟柱子进入的过程,ans表示上一个柱子停留的地点,该柱子面积为x。
如果最后一个>=x的柱子的pos<ans,则ans=pos,否则ans--
最后一个>=x的柱子显然可以二分得到,直接uppper_bound-1即可
代码:
View Code
总算碰到了一道水题。。。
考虑到如果下一个圆柱比上一个圆柱面积大,那么它的有效面积也只能是上一个圆柱的面积,所以不妨就把它的面积记为上一个圆柱的面积。
然后我们得到了一个单调下降的面积序列。
然后我们模拟柱子进入的过程,ans表示上一个柱子停留的地点,该柱子面积为x。
如果最后一个>=x的柱子的pos<ans,则ans=pos,否则ans--
最后一个>=x的柱子显然可以二分得到,直接uppper_bound-1即可
代码:
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm>10 11 #include<iostream>12 13 #include<vector>14 15 #include<map>16 17 #include<set>18 19 #include<queue>20 21 #include<string>22 23 #define inf 100000000024 25 #define maxn 300000+526 27 #define maxm 500+10028 29 #define eps 1e-1030 31 #define ll long long32 33 #define pa pair<int,int>34 35 #define for0(i,n) for(int i=0;i<=(n);i++)36 37 #define for1(i,n) for(int i=1;i<=(n);i++)38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)42 43 #define mod 100000000744 45 using namespace std;46 47 inline int read()48 49 {50 51 int x=0,f=1;char ch=getchar();52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}56 57 return x*f;58 59 }60 int n,m,tot,a[maxn],b[maxn];61 62 int main()63 64 {65 66 freopen("input.txt","r",stdin);67 68 freopen("output.txt","w",stdout);69 70 n=read();m=read();a[tot=1]=-read();71 for2(i,2,n)a[i]=max(-read(),a[i-1]);72 int ans=n+1;73 for1(i,m)74 {75 int x=upper_bound(a+1,a+n+1,-read())-a-1;76 if(x>=ans)ans--;else ans=x;77 }78 printf("%d\n",ans<=0?0:ans);79 80 return 0;81 82 }
BZOJ1510: [POI2006]Kra-The Disks
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。