Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴代码,千万不要自己写排序算法,用冒泡排序是超时的。。。还是用stl的sort函数吧

Posted by Saleed at 2016-08-23 21:38:44 on Problem 2431
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator