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

求问为什么会wa??被这道题卡死了···

Posted by xuesu at 2014-01-25 16:26:30 on Problem 2431
代码如下
#include<iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> pr;
pr a[10000];
int heap[10000],sz=0;//模拟根值最大的树
int push(int x){//模拟树的更新
	int i =sz++;
	while( i>0){
		int p=(i-1)/2;
		if(heap[p]>=x)break;
		heap[i ]=heap[p];
		i=p;
	}
	heap[i]=x;
	return 0;
}
int pop(){//清除并返回根值同时更新
	int ret=heap[0];
	int x=heap[--sz];
	int i=0;
	while(2*i+1<sz){
		int a=2*i+1;
		int b=2*i+2;
		if(b<sz&&heap[b]<heap[a])a=b;
		if(heap[a]<x)break;
		heap[i]=heap[a];
		i=a;
	}
	heap[i]=x;
	return ret;
}
int cmp(const pr p1,const pr p2){
	if(p1.first>p2.first)return 1;
	else return 0;
}
int main(){
	int n,l,p,i=0,ans=0,flag=0;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i].first>>a[i].second;
	}
	cin>>l>>p;
	sort(a,a+n,cmp);//排序剩余距离
	l-=p;
	while(l>0){//循环直到到达或超过终点
		for(;a[i].first>=l;i++){
			push(a[i].second);//把可以到达的加油站油量加入队列
		}
		if(sz==0){flag=1;break;//如果不存在可加的油就返回false
		}
		p=pop();//从队列中清除已经加过油的加油站
		l-=p;
		ans++;
	}
	if(flag)cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}

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