栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 3285 Tower III

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 3285 Tower III

#include<iostream>#include<cstdio>#include<cstring>#include<map>#include<algorithm>using namespace std;struct Point{int x,y;bool friend operator<(Point a,Point b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;}Point(){}Point(int xx,int yy){x=xx;y=yy;}};map<Point,int>mp;struct Unit{int l,r,x,y,id;bool friend operator<(Unit a,Unit b){return a.x>b.x;}};Unit ut[1005];int N,W,C,D;double val[1005];int f_max(int x,int y){return x>y?x:y;}void get_data(){int i;mp.clear();for(i=0;i<N;i++){scanf("%d%d",&ut[i].x,&ut[i].y);ut[i].l=ut[i].r=-1;}sort(ut,ut+N);for(i=0;i<N;i++){mp[Point(ut[i].x,ut[i].y)]=i;}Point t;memset(val,0,sizeof(val));int fg;for(i=0;i<N;i++){fg=0;t.x=ut[i].x-1;t.y=ut[i].y-1;if(mp.find(t)!=mp.end())ut[i].l=mp[t],fg++;t.x=ut[i].x-1;t.y=ut[i].y+1;if(mp.find(t)!=mp.end())ut[i].r=mp[t],fg++;if(fg==1){if(ut[i].l!=-1)val[ut[i].l]+=val[i]+W;if(ut[i].r!=-1)val[ut[i].r]+=val[i]+W;}else if(fg==2){val[ut[i].l]+=(val[i]+W)*1.0/2;val[ut[i].r]+=(val[i]+W)*1.0/2;}}sort(val,val+N);int tt,cnt=0;if(val[N-1]>C)tt=0;else{tt=(C-val[N-1])/D;while(tt*D<=C-val[N-1])tt++;}for(i=N-1;i>=0;i--){if(val[i]>f_max(0,C-D*tt))cnt++;}if(!cnt)printf("-1n");else printf("%d %dn",tt,cnt);}int main(){while(scanf("%d%d%d%d",&N,&W,&C,&D)!=EOF){get_data();}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/379709.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号