首页 > 代码库 > HDU 4393 Throw nails
HDU 4393 Throw nails
http://acm.hdu.edu.cn/showproblem.php?pid=4393
题意:有n个人,i-th人第一秒速度为Fi/s,之后Si/s。每一秒末,跑在最前面的人消失,如果有多个人同时在最前面,id最小的人消失。输出消失顺序。
题解:因为Si最多只有100个,所以对Si进行操作。采用优先队列,相同Si的压进相同的队列。求每一次最大的Fi+Si*t。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <queue> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int maxn=50010; 10 11 struct node{ 12 int F,S,id; 13 bool operator<(const node &x) const { 14 if(F!=x.F) return F<x.F; 15 return id>x.id; 16 } 17 }P[maxn]; 18 19 priority_queue<node> pque[110]; 20 21 int main() 22 { 23 //freopen("/Users/apple/Desktop/codeblocks/D.txt","r",stdin); 24 25 int T,n; 26 scanf("%d",&T); 27 for(int ca=1;ca<=T;ca++) 28 { 29 scanf("%d",&n); 30 for(int i=0;i<n;i++) 31 { 32 scanf("%d%d",&P[i].F,&P[i].S); 33 P[i].id=i+1; 34 pque[P[i].S].push(P[i]); 35 } 36 int t; 37 node tmp; 38 int mtime=0; 39 int ide; 40 int k; 41 printf("Case #%d:\n",ca); 42 int flag=1; 43 int flag1=n; 44 while(n--) 45 { 46 flag++; 47 t=-1; 48 for(int i=1;i<=100;i++) 49 { 50 51 if(!pque[i].empty()) 52 { 53 tmp=pque[i].top(); 54 if(tmp.F+tmp.S*mtime>t) 55 { 56 t=tmp.F+tmp.S*mtime; 57 ide=tmp.id; 58 k=i; 59 } 60 else if(tmp.F+tmp.S*mtime==t) 61 { 62 if(tmp.id<ide) 63 { 64 ide=tmp.id; 65 k=i; 66 } 67 } 68 } 69 } 70 if(!pque[k].empty()) pque[k].pop(); 71 if(flag==flag1+1) printf("%d\n",ide); 72 else printf("%d ",ide); 73 mtime++; 74 } 75 } 76 return 0; 77 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。