074_주유소 문제(우선 대기열)

주유소 문제, 한 대의 차는 주유소마다 일정 수량의 기름을 넣을 수 있고, 메일박스 용량은 상한선이 없다. 한 단위의 노정으로 가면 한 단위의 기름을 소모한다. 자동차가 종점에 도달할 수 있는지, 가능하다면 최소한 몇 번의 기름을 넣을 수 있는지 물어본다.이 관점에서 문제를 생각하는 것이 비교적 편리하다.
자동차가 어느 주유소를 지나갈 때, 기름만 차에 싣고, 오일 탱크에 넣지 않는다.오일 탱크가 비어 있을 때 다시 주유하는 것은 주유소에서 주유하는 효과와 일치한다.(도전 프로그램 경연대회 2판은 한 번의 응원의 기회를 얻었다고 한다)
그래서 오일 탱크가 다 떨어졌을 때 가장 큰 기름통을 선택해 메일박스에 넣으면 된다.
XCODE C++ 코드는 다음과 같습니다.
//
//  074_expedition.cpp
//  changlle
//
//  Created by user on 12/29/15.
//  Copyright (c) 2015 user. All rights reserved.
//

#include 
#include 
#include 
using namespace std;

int N=4;
int L=25;
int P=10;
int A[4]={10,14,20,21};
int B[4]={10,5,2,4};


int main() {
    
    int tank=P;
    priority_queue que;
    que.push(0);
    int D[4];
    D[0]=A[0];
    for (int i=1;i<4;i++)
        D[i]=A[i]-A[i-1];
    
    int count=0;
    int i=0;

    
    while(i<=3) {
        
        if (tank-D[i]<0)
          {
              
              if(que.empty()){
                  count=-1;
                  break;
                  
              }
             
              tank=tank+que.top();
              cout<

좋은 웹페이지 즐겨찾기