10.1综合强化刷题 Day4
财富(treasure)
Time Limit:1000ms Memory Limit:128MB
题目描述
LYK有n个小伙伴。每个小伙伴有一个身高hi。
这个游戏是这样的,LYK生活的环境是以身高为美的环境,因此在这里的每个人都羡慕比自己身高高的人,而每个人都有一个属性ai表示它对身高的羡慕值。
这n个小伙伴站成一列,我们用hi来表示它的身高,用ai来表示它的财富。
每个人向它的两边望去,在左边找到一个最近的比自己高的人,然后将ai朵玫瑰给那个人,在右边也找到一个最近的比自己高的人,再将ai朵玫瑰给那个人。当然如果没有比自己身高高的人就不需要赠送别人玫瑰了。也就是说一个人会给0,1,2个人玫瑰(这取决于两边是否有比自己高的人)。
每个人都会得到若干朵玫瑰(可能是0朵),LYK想知道得了最多的玫瑰的那个人得了多少玫瑰。(然后嫁给他>3<)
输入格式(treasure.in)
第一行一个数n表示有n个人。
接下来n行,每行两个数hi,ai。
输出格式(treasure.out)
一个数表示答案。
输入样例
3
4 7
3 5
6 10
输出样例
12
样例解释
第一个人会收到5朵玫瑰,第二个没人送他玫瑰,第三个人会收到12朵玫瑰。
数据范围
对于50%的数据n<=1000,hi<=1000000000。
对于另外20%的数据n<=50000,hi<=10。
对于100%的数据1<=n<=50000,1<=hi<=1000000000。1<=ai<=10000。
一个简单的单调栈
我们跑两遍单调栈,先正着跑一遍(处理出每一个人给右边第一个比他高的),在倒着跑一遍(处理出每个人把花给他左边第一个比他高的)
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 1000010 using namespace std; int n,ans,sum[N],q[N],h[N],a[N],stack[N]; int read() { ,f=; char ch=getchar(); ') ch=getchar(); +ch-',ch=getchar(); return x*f; } int main() { // freopen("treasure.in","r",stdin); // freopen("treasure.out","w",stdout); n=read(); ;i<=n;i++) h[i]=read(),a[i]=read(); ,i=;i<=n;i++) { while(top&&stack[top]<=h[i]) top--; sum[q[top]]+=a[i]; stack[++top]=h[i];q[top]=i; } ,i=n;i>=;i--) { while(top&&stack[top]<=h[i]) top--; sum[q[top]]+=a[i]; stack[++top]=h[i];q[top]=i; } ;i<=n;i++) ans=max(ans,sum[i]); printf("%d",ans); ; }
AC代码
正方形(square)
Time Limit:1000ms Memory Limit:128MB
题目描述
在一个10000*10000的二维平面上,有n颗糖果。
LYK喜欢吃糖果!并且它给自己立了规定,一定要吃其中的至少C颗糖果!
事与愿违,LYK只被允许圈出一个正方形,它只能吃在正方形里面的糖果。并且它需要支付正方形边长的价钱。
LYK为了满足自己的求食欲,它不得不花钱来圈一个正方形,但它想花的钱尽可能少,你能帮帮它吗?
输入格式(square.in)
第一行两个数C和n。
接下来n行,每行两个数xi,yi表示糖果的坐标。
输出格式(square.out)
一个数表示答案。
输入样例
3 4
1 2
2 1
4 1
5 2
输出样例
4
样例解释
选择左上角在(1,1),右下角在(4,4)的正方形,边长为4。
数据范围
对于30%的数据n<=10。
对于50%的数据n<=50。
对于80%的数据n<=300。
对于100%的数据n<=1000。1<=xi,yi<=10000。
当我看到这个题的时候就在想,这不就是个求最小的矩形,并且使这个矩形中的糖果的个数是否大于了c。然后蒟蒻本质暴露了出来,我企图用一个前缀和统计每个矩形内的糖果个数,然后在暴力枚举矩形边长和右下断点,判断是否合理,结果数组不是开大了就是开小了,直接崩溃
如果我们打算要用上面的做法的话我们需要离散化一下里面的点,不然最后一个点可能出现在10000,10000上,这样我们用一个前缀和处理的话会崩溃。
我们来看一下正解,数据范围在1000以内,能承受的时间复杂度为n^2logn的。
我们可以试着二分一下,二分矩形的边长,然后我们再试着枚举左边界,通过左边界我们就可以知道右边界,同样通过右边界我们也可以知道左边界,然后我们再在通过左右边界来判断里面的糖果数是否足够,当然我们的上下也是有边界的,我们在当前左右所加的这个矩形里,如果糖果数不够c那么直接返回false,反之,我们在来判断一下在这个区间里每个糖果的y坐标排序,然后将这个糖果的y与他的前c个糖果的y比较,如果小于等于mid的话,说明在这样的长度里我们可以找到c个糖果。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 1010 using namespace std; int c,n,L,R,mid,ans,cnt,tmp[N]; int read() { ,f=; char ch=getchar(); ; ch=getchar();} +ch-',ch=getchar(); return x*f; } struct Node { int x,y; }a[N]; int cmp(Node a,Node b) { return a.x<b.x; } int work(int l,int r) { <c) return false; cnt=; for(int i=l;i<=r;i++) tmp[++cnt]=a[i].y; sort(tmp+,tmp++cnt); for(int i=c;i<=cnt;i++) ]<=mid) return true; return false; } int pd(int x) { ; ;r<=n;r++) { if(a[r].x-a[l].x>x) { )) return true; while(a[r].x-a[l].x>x) l++; } } if(work(l,n)) return true; return false; } int main() { c=read(),n=read(); ;i<=n;i++) a[i].x=read(),a[i].y=read(); sort(a+,a++n,cmp); L=,R=,mid=(L+R)/; while(L<=R) { ,R=mid-,mid=(L+R)/; ,mid=(L+R)/; } printf("%d",ans); ; } AC代码
AC代码
追逐(chase)
Time Limit:1000ms Memory Limit:128MB
题目描述
这次,LYK以一个上帝视角在看豹子赛跑。
在一条无线长的跑道上,有n只豹子站在原点。第i只豹子将在第ti个时刻开始奔跑,它的速度是vi/时刻。
因此在不同的时刻,这n只豹子可能在不同的位置,并且它们两两之间的距离也将发生变化。
LYK觉得眼光八方太累了,因此它想找这么一个时刻,使得最远的两只豹子的距离尽可能近,当然这不能是第0时刻或者第0.01时刻。它想知道的是最迟出发的豹子出发的那一刻开始,离得最远的两只豹子在距离最小的时候这个距离是多少。
当然这个时刻不仅仅可能发生在整数时刻,也就是说可能在1.2345时刻这个距离最小。
输入格式(chase.in)
第一行一个数n。
接下来n行,每行两个数分别是ti和vi。
输出格式(chase.out)
输出一个数表示答案,你只需保留小数点后两位有效数字就可以了。
输入样例
3
1 4
2 5
3 7
输出样例
0.33
样例解释
在第5+2/3这个时刻,第一只豹子在18+2/3这个位置,第二只豹子在18+1/3这个位置,第三只豹子在18+2/3这个位置,最远的两只豹子相距1/3的距离,因此答案是0.33。
数据范围
对于20%的数据n=2。
对于20%的数据n=3
对于60%的数据n<=100。
对于80%的数据n<=1000。
对于100%的数据n<=100000,1<=vi,ti<=100000。
看到这个题的部分分,然后很开心,前两个点可以特判的、、
前4个点,也可以手算的,就是有点麻烦,所以蒟蒻在考场中并没有写、、、
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 1100 using namespace std; int n,t[N],v[N]; double ans; int read() { ,f=; char ch=getchar(); ') ch=getchar(); +ch-',ch=getchar(); return x*f; } int work1() { ]<t[]&&v[]>=v[]) ans=v[]*(t[]-t[]); ]<t[]&&v[]<v[]) ans=; ]<t[]&&v[]>=v[]) ans=v[]*(t[]-t[]); ]<t[]&&v[]<v[]) ans=; } int work2() { ans=0.33; } int main() { freopen("chase.in","r",stdin); freopen("chase.out","w",stdout); n=read(); ;i<=n;i++) t[i]=read(),v[i]=read(); ) work1(); else work2(); printf("%.2lf",ans); ; }
20分的特判
然后我们来看正解
什么?!竟然是解析几何?!啊啊啊,这题没法做了!
弃疗吧、、
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> using namespace std; *; ]; ],vv2[]; ],S[]; ]; int cmp(node i,node j) {return i.v<j.v || i.v==j.v && i.t>j.t;} ]; int CMP(Node i,Node j) {return i.x<j.x;} long double work(int x,long double y) {return (long double)t[x].v*y-hh[x];} int main() { freopen("chase.in","r",stdin); freopen("chase.out","w",stdout); ) { scanf("%d",&n); // if (n==0) return 0; MAX=; ; i<=n; i++) { scanf("%d%d",&t[i].t,&t[i].v); MAX=max(MAX,t[i].t); } sort(t+,t+n+,cmp); int MIN=t[n].t; ; i>=; i--) { ; else MIN=t[i].t,vv[i]=; } ; i<=n; i++) hh[i]=(long double)t[i].t*t[i].v; r=; s[].l=MAX; s[].t=; s[].l=INF; vv[n]=; ; i<=n; i++) if (!vv[i]) { while (r && work(i,s[r].l)>=work(s[r].t,s[r].l)) r--; ; s[].l=MAX; s[].t=i; continue;} L=s[r].l; R=s[r+].l; mid=(L+R)/2.0; ; I<=; I++) { if (work(i,mid)>=work(s[r].t,mid)) {R=mid; mid=(L+R)/2.0;} else {L=mid; mid=(L+R)/2.0;} } s[++r].l=mid; s[r].t=i; s[r+].l=INF; } rr=; S[].l=MAX; S[].l=INF; S[].t=n; MIN=t[].t; ; i<n; i++) ; else MIN=t[i].t,vv2[i]=; ; i>=; i--) if (!vv2[i]) { while (rr && work(i,S[rr].l)<=work(S[rr].t,S[rr].l)) rr--; ; S[].l=MAX; S[].t=i; continue;} L=S[rr].l; R=S[rr+].l; mid=(L+R)/2.0; ; I<=; I++) { if (work(i,mid)<=work(S[rr].t,mid)) {R=mid; mid=(L+R)/2.0;} else {L=mid; mid=(L+R)/2.0;} } S[++rr].l=mid; S[rr].t=i; S[rr+].l=INF; } cnt=; ; i<=r; i++) {p[++cnt].x=s[i].l; p[cnt].y=; p[cnt].z=s[i].t;} ; i<=rr; i++) {p[++cnt].x=S[i].l; p[cnt].y=; p[cnt].z=S[i].t;} sort(p+,p+cnt+,CMP); X=Y=; ans=INF; ; i<=cnt; i++) { ) X=p[i].z; else Y=p[i].z; // printf("%.5f\n",(double)p[i].x); if (X && Y) ans=min(ans,work(X,p[i].x)-work(Y,p[i].x)); } printf("%.2f\n",fabs((double)ans)); ; } }
标程
最新文章
- 使用html5 地理位置技术 和 百度地图api查询当前位置
- 移动应用开发过程中需要哪些IOS APP工具
- switch多分支语句简析
- CSS3系列三(与背景边框相关样式 、变形处理、动画效果)
- c3p0数据库连接池
- ArcGIS操作问题
- 基本NT式驱动代码结构
- HTML系列(二):头部meta元素
- xp安装maven
- MacOS 下安装mysqlclient 的问题及解决办法
- AIO5岗位桌面主页【我的收藏夹】只显示8行,怎样增加显示行?
- jdk 环境配置踩坑
- Docker常见仓库WordPress
- MinGW GCC 7.2.0 2017年8月份出炉啦
- C++探究foreach算法
- sqlserver数据库的分离与附加
- 简单的Excel导入(上传、解析、持久化)
- Python pyQt4/pyQt5 学习笔记2(状态栏、菜单栏和工具栏)
- Linux——系统开关机指令简单学习笔记
- java面试第四天