| ||||||||||
| 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