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 Renegade at 2006-09-18 22:45:46 on Problem 2431
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 10001;

struct Stop {
    int dist,fuel;
};

bool operator < (const Stop & a, const Stop & b)
{
    return a.fuel < b.fuel;
}

bool cmp (const Stop & a,const Stop & b)
{
    return a.dist < b.dist;
}

int N,L,P;
Stop stop[MAXN];
priority_queue<Stop> hp;

int main()
{
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d %d",&stop[i].dist,&stop[i].fuel);
    }
    scanf("%d %d",&L,&P);
    sort(stop,stop+N,cmp);
    bool flag=true;
    int stops=0;
    for(int i=0;i<N;i++){
        hp.push(stop[i]);
        if(stop[i].dist > L)continue;
        while(stop[i].dist > P){
            if(hp.size()==0){flag=false; break;}
            stops++;
            P+=hp.top().fuel;
            hp.pop();
        }
    }
    while(L > P){
        if(hp.size()==0){flag=false; break;}
        stops++;
        P+=hp.top().fuel;
        hp.pop();
    }
    if(!flag)puts("-1");
    else printf("%d\n",stops);
}

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