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

过不去,求助。。。

Posted by wirehack at 2015-05-24 21:47:49 on Problem 2431 and last updated at 2015-05-24 23:07:33
#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:
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