1033 To Fill or Not to Fill

Sample Input 1:

50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300

Sample Output 1:

749.17

Sample Input 2:

50 1300 12 2
7.10 0
7.00 600

Sample Output 2:

The maximum travel distance = 1200.00

题目大意

给你杭州到某城市的距离ending，假设他们之间是一条直线，然后在这直线上有M个加油站，每个加油站卖的汽油价格都不一定相同。排除所有干扰因素，固定车子每升油可行驶avg距离，一开始车子是木有一滴油的，告诉你ending，M，avg，以及车子油箱的最大容量MAXSIZE，求杭州到某城市所需最少的油费，如果无法抵达，输出最远可行驶的距离。结果保留两位有小数。

思路

注意，一开始就没有加油站的情况。然后贪心思想，如果从加油站A出发，在接下来的MAXSIZE*avg距离内，存在价格比A更低的站点B，那我们只需要保证剩下的油可以抵达B即可，否则把在A帮邮箱加满

C/C++ 

#include
using namespace std;
struct Station{
    double price;
    int index;
    bool friend operator <(const Station &x,const Station &y){
        return x.index < y.index;
    }
}s[501];
int MAXSIZE,ending,avg,M;
double OP();
int main()
{
    cin >> MAXSIZE >> ending >> avg >> M;
    for(int z=0;z> s[z].price >> s[z].index;
    s[M].index = ending;
    sort(s,s+M);
    double result = OP(); // 利用 result 的正负判断终点是否能抵达
    if(result==0) cout << "The maximum travel distance = 0.00" << endl;
    else if(result<0) printf("The maximum travel distance = %.02f",-result);
    else printf("%.2f",result);
    return 0;
}
double OP(){
    if(s[0].index!=0) return 0;
    double sum=0,len=0;             // 总消费,当前油可行驶记录
    int now = 0,maxLen=MAXSIZE*avg; // 当前位置,邮箱最大行驶距离
    while (now!=M){
        bool ok = false; // 判断从s[now]出发,是否能遇到更便宜油价的站点
        int next = now+1,flag=now+1;
        if(s[next].index > s[now].index+maxLen) return -(s[now].index + maxLen);
        while (s[now].index+maxLen>=s[next].index) {
            if (s[next].price <= s[now].price) {
                if (len < s[next].index) sum += (s[next].index - len) * 1.0 / avg * s[now].price;
                len = s[next].index;
                now = next;
                ok = true;
                break;
            } else if (s[next].price < s[flag].price) flag = next;
            next++;
        }
        if(!ok){
            sum += (maxLen-len+s[now].index)*1.0/avg * s[now].price;
            len = s[now].index + maxLen;
            now = flag;
        }
    }
    return sum;
}