学步园

这是一道贪心的经典题目

感觉自己出数据，出数据，弄得自己思维比较乱

总是往“找反例”这里钻 自己刚有一点思路，脑袋里就蹦出来来好几种“反例”情况，还有各种假设。。

然后就是要各种说服自己的节奏了，这过程艰难那。。

确实很久没认真过题了 模拟一直是我的弱项

这道题昨晚开始做的 今早才做出来

题中从起点到终点  要看你是怎么看待中途的一个个加油站，这是一个个“子问题”，

在这“子问题”要怎样才能做到足够的贪心呢？

关键在于你如何判断去下一个站：看从当前这个站加满油出发能走多远，在这段距离中找第一个比当前站油价要低的站，

                            如果存在，

                                              油的剩余量不够的话，我们就从当前站加适量的油，使其刚好能到那个价低的站。

                                              油的剩余量够的话，就直接计算到达价低的站的剩余量。  

                           如果不存在，我们就加满油去紧邻着的那个站，并计算出到达紧邻站时 油的剩余量。

还有一点收获就是在题目存在反例的时候，我发现用函数操作会比较好，遇到符合反例的条件就直接return出来，不要像以前那样，想好几个限制性条件来规范的输出反例。

就这些吧。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
double d1,c,d2,p,n;
double i[22],dis[22],pi[22],x[22],shen[22];
double h,flag,len,sum;
int j,k;
double go()
{
    len = c*d2;
    shen[0] = 0;
    for( k = 0; k <= n;)
    {
        j = k + 1;
        if(dis[j] - dis[k] > len) return 0;
        while(dis[j] - dis[k] <= len && j <= n)
        {
            if(pi[j] < pi[k])break;
            j++;
        }

        if(dis[j] - dis[k] < len)
        {
            if(shen[k]*d2 >= dis[j] - dis[k])
                shen[j] = shen[k] - (dis[j] - dis[k])/d2;
            else
                x[k]=(dis[j] - dis[k])/d2 - shen[k];
        }
        else
        {
            x[k] = c - shen[k];
            j = k + 1;
            shen[j] = c - (dis[j]-dis[k])/d2;
        }
        k=j;
    }
    sum=0;
    for(int f = 0; f <= n; f++)
        sum += x[f]*pi[f];
    return sum;
}
int first()
{
    while(cin>>d1)
    {
        memset(pi,0,sizeof(pi));
        memset(i,0,sizeof(i));
        memset(dis,0,sizeof(dis));
        memset(x,0,sizeof(x));
        flag = 0;
        cin>>c>>d2>>pi[0]>>n;
        for(k = 1; k <= n; k++)
            cin>>dis[k]>>pi[k];
        dis[k] = d1;
        flag = go();
        if(!flag)cout<<"No Solution"<<endl;
        else
        {
            cout.setf(ios::fixed);
            cout.precision(2);
            cout<<flag<<endl;
        }
    }
    return 0;
}
int main()
{
    //freopen("11.txt","r",stdin);
    first();
    return 0;
}