当前位置：首页 -> 基础 -> c++编程基础

1033. To Fill or Not to Fill (25)

2014-11-24 02:02:49 · 作者: · 浏览: 6
标签: 1033. Fill Not
网上策略说的很详细了，利用贪心算法：
假设我们现在在A点，A能到达的最远距离之内有B, C, D三个点：
1. 如果B， C， D中有比A小的，则找到离A最近的，A加的油刚好够到这个点；
2. 如果没有比A小的，A加满油，到B\C\D中最小的一个点停下来，再加油。
代码注意细节：当第一个点距离不是0时，车子哪里都去不了！ 
#include   
#include   
#include   
#include   
#include   
using namespace std;  
  
double a, b, c, d;  
struct node  
{  
    double price;  
    double dist;  
    node(double p, double d): price(p), dist(d) {}  
};  
vector v;  
bool finished = false;  
double cost = 0;  
  
bool cmp(const node &n1, const node &n2)  
{  
    return n1.dist < n2.dist;  
}  
  
double fillOrNot(int index, double left)  
{  
    double fastest = v[index].dist + c * a;  
    if(index + 1 < d && (v[index + 1].dist - v[index].dist) > c * a)  
    {  
        cost += v[index].price * (a - left);  
        return fastest;  
    }  
    else if(index + 1 == d && (b - v[index].dist) > c * a)  
    {  
        cost += v[index].price * (a - left);  
        return fastest;  
    }  
    /*if(fastest >= b) 
    { 
        cost += ((b - v[index].dist)/c - left) * v[index].price; 
        finished = true; 
        return 0.0; 
    }*/  
    int smallest = index + 1;  
    for(int i = index + 1; i < d && v[i].dist < fastest; i++)  
        if(v[index].price >






 v[i].price)  
        {  
            cost += ((v[i].dist - v[index].dist)/c - left)*v[index].price;  
            return fillOrNot(i, 0);  
        }  
        else if(v[smallest].price > v[i].price)  
            smallest = i;  
    //如果没有比当前便宜的  
    if(fastest >= b)  
    {//如果当前可以到终点，直接到  
        cost += ((b - v[index].dist)/c - left) * v[index].price;  
        finished = true;  
        return 0.0;  
    }  
    else  
    {  
        cost += (a - left) * v[index].price;  
        return fillOrNot(smallest, a - (v[smallest].dist - v[index].dist)/c);  
    }  
}  
  
int main()  
{  
//  fstream cin("a.txt");  
    cin>>a>>b>>c>>d;  
    double tmp1;  
    double tmp2;  
    for(int i = 0; i < d; i++)  
    {  
        cin>>tmp1>>tmp2;  
        node n(tmp1, tmp2);  
        v.push_back(n);  
    }  
    sort(v.begin(), v.end(), cmp);  
    double fastest = fillOrNot(0, 0.0);  
    if(v[0].dist != 0)  
    {  
        cout<<"The maximum travel distance = 0.00"<