최소 정지 수를 찾는 욕심 많은 알고리즘

Question

Mr X는 고속도로에서 차로 여행합니다. 도중에 가스 (주유소)가 여러 개 있다고 가정 해 보겠습니다. 거리 0 = d0 < d1 < d2 < ... < dn부터 출발점 d0까지.

미스터 X'scar가 가득 차면 거리 D> = max {di + 1-di}만큼 이동할 수 있습니다. X 씨는 가스를 채우는 횟수를 최소화하려고합니다.

필요한 최소 정지 횟수를 반환하는 그리 디 알고리즘을 작성합니다.

Answer 1

이것은 일종의 요구 사항입니다.

GCC 4.8.3 : g++ -Wall -Wextra -std=c++0x -g main.cpp

#include <algorithm> 
#include <iostream> 
#include <stdexcept> 
#include <vector> 

int count_stops(int D, const std::vector<int>& d) { 
    if (d.size() < 2) { throw std::logic_error("Vector too small."); } 

    auto p = std::begin(d); 
    auto count = 0; 

    while (p != --std::end(d)) { 
    // Greedy: go as far as I can on this tank of gas. 
    auto n = --std::find_if(p, std::end(d), [=](int x) { 
     return *p + D < x; }); 
    // The specification says we do not need to worry about this... 
    if (p == n) { throw std::logic_error("D too small."); } 
    p = n; 
    ++count; } 

    return count; } 


int main(int, char* []) { 
    auto D = 16; 
    auto d = std::vector<int> { 0, 5, 15, 30, 32, 33, 37, 49, 53, 59, 61 }; 

    std::cout << "stops: " << count_stops(D, d) << "\n"; 
    return 0; }