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