Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴代码,千万不要自己写排序算法,用冒泡排序是超时的。。。还是用stl的sort函数吧#include<iostream> #include<queue> #include<algorithm> using namespace std; struct _pair{ int pos,station; }; bool cmp(const _pair &a1,const _pair &a2) { return a1.pos<a2.pos; } int main(){ int N,L,P; _pair *stop; cin>>N; stop=new _pair[N]; for(int i=N-1;i>=0;i--) cin>>stop[i].pos>>stop[i].station; cin>>L>>P; for(int i=0;i<N;i++) { stop[i].pos=L-stop[i].pos; //cout<<pos[i]<<station[i]<<endl; } /* for(int i=0;i<N;i++){ for(int j=1;j<N-i;j++){ if(pos[j]<pos[j-1]){ int tmp1=pos[j],tmp2=station[j]; pos[j]=pos[j-1];pos[j-1]=tmp1; station[j]=station[j-1];station[j-1]=tmp2; } } } */ sort(stop,stop+N,cmp); int tank=P,pss=0,dist=0,ans=0; priority_queue<int> que; while(tank>0){ dist+=tank; //cout<<dist<<endl; tank=0; while(pss<N&&dist>=stop[pss].pos){//条件一定要在判别式里面写完备,避免写嵌套式的判断式,很容易出错 que.push(stop[pss].station); pss++; } if(dist>=L) break; else if(que.empty()&&dist<L){ ans=-1; break; } else { tank+=que.top(); //cout<<tank<<endl;; que.pop(); ans++; } } cout<<ans<<endl; return 1; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator