| ||||||||||
| 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 | |||||||||
过不去,求助。。。#include <stdio.h>
#define MAX 200000
struct stop
{
int fuel;
int distance;
}stops[MAX]={0,0},heap[MAX]={0,0},truck;
int sz=0;
void push(struct stop);
struct stop del();
int main()
{
int n,i,count=0,j;
struct stop mfuel;
scanf("%d",&n);
for(i=0; i<n; i++)
scanf("%d %d",&stops[i].distance,&stops[i].fuel);
scanf("%d %d",&truck.distance,&truck.fuel);
while(truck.distance>0)
{
for(i=0,j=0; i<n; i++)
if(truck.distance>stops[i].distance && (truck.distance-stops[i].distance)<=truck.fuel)
{
push(stops[i]);
j=1;
}
truck.distance-=truck.fuel;
truck.fuel=0;
if(truck.distance<=0)
break;
mfuel=del();
truck.fuel=mfuel.fuel;
if(sz==0&&truck.fuel==0)
{
printf("-1\n");
return 0;
}
count++;
}
printf("%d\n",count);
return 0;
}
void push(struct stop x)
{
int i,p;
i=sz++;
while(i>0)
{
p=(i-1)/2;
if(x.fuel<=heap[p].fuel)
break;
heap[i]=heap[p];
i=p;
}
heap[i]=x;
}
struct stop del()
{
struct stop max=heap[0],x=heap[--sz];
int i=0,l,r;
while(i*2+1<sz)
{
l=i*2+1;
r=i*2+2;
if(r<sz && heap[r].fuel>heap[l].fuel)
l=r;
if(heap[l].fuel<=x.fuel)
break;
heap[i]=heap[l];
i=l;
}
heap[i]=x;
return max;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator