83 条题解

  • 3
    @ 2012-08-09 21:56:45

    贪心思想:

    首先预处理判断两个加油站的距离是否有可能在当前油箱容量上限下驶过,如果不能输出-1否则一定可以到达进行下面的计算

    在满油箱能抵达的加油站中查找(从近到远)

    如果有油价更便宜的,那么显然当前的油只要能到那里就可以了(油足直接开过去不足加到恰好过去为止)

    如果没有,那么加满油开到下一个加油站(可以证明一定是最优的)

    然后到最后一个加油站单独判断一次,最后输出总开销

    注意点:

    就列出来我错过的地方和注意事项(好多……)

    1、注意声明的类型(int和double如果错了可能能过但其实是有问题的)

    2、这道题输入是按距离排序好的不用排序,但是题目中没明确说明,所以要判断

    3、p和d不要写反否则有的地方写反了能过4个点……这渣数据!

    4、注意每个地方计算的时候最后改变油量和汽车位置,否则会影响到花销的计算和耗油量的计算

    5、注意最后计算直接抵达终点的油量不要写错(记着把能用的油用掉忘了的话会输出多一点的值)

    6、浮点数的大小比较……这个应该没事但是用gdb查中间变量的时候发现浮点数的真实值和输入值不是一模一样的

    7、保留两位小数的做法:先乘100,再四舍五入(round函数),再除以100,最后固定两位小数输出,否则比如1.90有可能被输出成1.9……

    然后别的仔细调试应该要是错就是无意中打错的。。(欢迎补充更多的错误类型)

  • 1
    @ 2021-09-04 17:11:29
    #include <bits/stdc++.h>
    using namespace std;
    
    #define maxn 100000
    #define db double
    #define INF 9999999 
    int n;
    db D1, D2, C, P, res, ans, maxx;
    struct node
    {
        db co, dis;
        bool friend operator<(const node& a, const node& b){
            return a.dis<b.dis;
        }
    }pl[maxn];
    
    int Solve(int now)
    {
        int flag=INF; db d=pl[now].dis; 
        for(int i=now+1; i<=n && pl[i].dis-d<=maxx; i++){
            if(pl[i].co < pl[now].co){
                ans += ((pl[i].dis - d - res) / D2) * pl[now].co;
                res = 0; return i;
            }
            if(flag==INF || pl[i].co<pl[flag].co)
                flag = i;
        }
        if(D1-pl[now].dis<=maxx){
            ans+=((D1-pl[now].dis-res)/D2)*pl[now].co;
            return INF;
        }
        if(flag==INF){
            cout<<"No Solution\n";
            return -1;
        }
        else{
            ans+=C*pl[now].co;
            res+=(maxx-(pl[flag].dis-d));
            return flag;
        }
    }
    
    int main()
    {
        cin>>D1>>C>>D2>>P>>n;
        pl[0].dis=0,pl[0].co=P;
        for(int i=1; i<=n; i++) 
            cin>>pl[i].dis>>pl[i].co;
        sort(pl,pl+n+1);
        maxx=C * D2;
        int k=0,t;
        do{
            t=Solve(k),k=t;
            if(t==-1)
                return 0;
        }
        while(t != INF);
        printf("%.2lf", ans);
        return 0;
    }
    
  • 1
    @ 2019-07-22 11:17:42

    发表一下题解以及我踩到的坑。首先说一下DP,我看到题目第一个思路就是DP,但是事实证明DP第四个点过不了,因为这个题目不满足最优子结构。到终点最优是刚好把油用完,但是在中间的油站却可以在油箱里留油,所以写DP默认都是到点刚好用完油的话,就达不到最优。DP代码如下:

    #include <iostream>
    #include <stdio.h>
    
    using namespace std;
    
    int n;
    double dp[102];
    double sta[102][2]={0};
    
    int main()
    {
        double a,b,c,f;
        cin>>a>>b>>c>>sta[0][1];
        int i,j;
        cin>>n;
        f=b*c;
        for(i=1;i<=n;i++)
        {
            cin>>sta[i][0]>>sta[i][1];
            if(sta[i][0]-sta[i-1][0]>f)
            {
                cout<<-1<<endl;
                return 0;
            }
        }
        dp[0]=0;
        sta[n+1][0]=a;
        for(i=1;i<=n+1;i++)
        {
            dp[i]=1e40;
            for(j=i-1;j>=0;j--)
            {
                if(sta[i][0]-sta[j][0]>f)
                {
                    break;
                }
                else
                {
                    dp[i]=min(dp[i],dp[j]+(sta[i][0]-sta[j][0])*sta[j][1]/c);
                }
            }
        }
        printf("%.2f\n",dp[n+1]);
        return 0;
    }
    

    转换思路改用贪心,首先了解到这样一个事实,车辆最多只能走(油箱/里程油耗)那么远。
    每次到达一个油站,在之后的油站中选取可达的。
    如果之后某一个油站第一次比当前油站价格低,则下一个加油点就是该油站。此时油箱只用留刚好到达下一个油站的钱就行。
    如果之后所有点都比当前油站价格高,那就在当前油站买满油,因为此时的油是可达范围内最便宜的。然后取可达范围内价格最低的油站作为下一个买油点。
    贪心代码如下:

    #include <iostream>
    #include <stdio.h>
    
    using namespace std;
    
    int n;
    double a,b,c,f;
    double sta[102][2]={0};
    
    int nextsta(int now)
    {
        int i=now+1,next=now+1;
        while(sta[i][0]-sta[now][0]<=f)
        {
            if(sta[i][1]<sta[now][1])
            {
                next=i;
                break;
            }
            else if(sta[i][1]<sta[next][1])
            {
                next=i;
            }
            i++;
        }
        return next;
    }
    
    double buy(double &yx,int &now,int next)//当前油站买油
    {
        double ans=0;
        double d=sta[next][0]-sta[now][0];
        if(sta[next][1]<sta[now][1])
        {
            ans=(d/c-yx)*sta[now][1];
            yx=0;
            now=next;
        }
        else
        {
            ans=(b-yx)*sta[now][1];
            yx=b-d/c;
            now=next;
        }
        return ans;
    }
    
    int main()
    {
        cin>>a>>b>>c>>sta[0][1];
        int i,j;
        double ans=0,yx=0;
        cin>>n;
        f=b*c;
        for(i=1;i<=n;i++)
        {
            cin>>sta[i][0]>>sta[i][1];
            if(sta[i][0]-sta[i-1][0]>f)
            {
                cout<<-1<<endl;
                return 0;
            }
        }
        sta[n+1][0]=a;
        i=0;
        while(i<n+1)
        {
            j=nextsta(i);
            ans+=buy(yx,i,j);
        }
        printf("%.2f\n",ans);
        return 0;
    }
    
  • 1
    @ 2018-08-15 21:02:13

    mdzz
    完全不知道为什么错的情况下调了半个小时,然后发现自己为了四舍五入写了这么个东西

    printf("%.2lf",ans+0.005);
    

    然后第四个点就华丽丽地卡死了,去掉以后就过了
    我这是写了个什么玩意

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    struct node{
        double d,p;
    }q[110];
    
    int cmp(const node&x,const node&y)
    {
        return x.d<y.d;
    }
    
    int main()
    {
        double d1,c,d2,p,you=0.0,fei=0.0,minn,ans=10000000.0;
        int n,i,j,now,hao,hao2;
        cin>>d1>>c>>d2>>p>>n;
        for(i=1;i<=n;i++)
        {
            cin>>q[i].d>>q[i].p;
        }
        q[0].d=0.0;
        q[0].p=p;
        q[n+1].d=d1;
        q[n+1].p=-100000.0;
        sort(q,q+n+2,cmp);
        for(i=1;i<=n+1;i++)
        {
            if((q[i].d-q[i-1].d)>c*d2)
            {
                cout<<-1;
                return 0;
            }
        }
        now=0;
        while(now<=n)
        {
            minn=100000000.0;
            hao=0;
            hao2=0;
            if(q[n+1].d-q[now].d<c*d2)
            {
                if(q[n+1].d-q[now].d>you*d2)
                 ans=min(ans,fei+q[now].p*((q[n+1].d-q[now].d)/d2-you));
            }
            for(j=now+1;j<=n+1;j++)
            {
                 if((q[j].d-q[now].d)>c*d2)
                  break;
                 if(q[j].p<q[now].p)
                 {
                    hao=j;
                    break;
                 }
                 if(q[j].p<minn)
                 {
                    minn=q[j].p;
                    hao2=j;
                 }
            }
            if(hao)
            {
                if(q[hao].d-q[now].p<you*d2)
                {
                    you-=(q[hao].d-q[now].d)/d2;
                }
                else
                {
                    fei+=q[now].p*((q[hao].d-q[now].d)/d2-you);
                    you=0;
                }
            }
            else
            {
                fei+=q[now].p*(c-you);
                you=c-(q[hao2].d-q[now].d)/d2;
            }
            if(hao)
             now=hao;
            else
             now=hao2;
        }
        printf("%.2lf",ans);
        return 0;
    }
    
  • 0
    @ 2022-04-10 16:54:28
    
    #include<iostream>
    #include<algorithm>
    #include<iomanip>
    using namespace std;
    
    int main()
    {
        float D1, C, D2, P, N;
        float Ds[1000][2];
        float minMoney = 0;
        cin >> D1 >> C >> D2 >> P >> N;
        Ds[0][0] = 0;
        Ds[0][1] = P;
        int i;
        for (i = 1; i <= N; i++)
        {
            cin >> Ds[i][0] >> Ds[i][1];
        }
        Ds[i][0] = D1;
        Ds[i][1] = 0;
    
        float NowP = P;
        float NowD = 0;
        int Flag_N = 0;
        bool isAble = true;
    
    
        for (int i = 1; i <= N + 1; i++)
        {
            if (Ds[i][0] - Ds[i-1][0] > (C * D2))
            {
                cout << "No Solution";
                isAble = false;
                break;
            }
            if (Ds[i][0] - Ds[Flag_N][0] > ((C * D2)))
            {
                NowD = Ds[Flag_N][0] + (C * D2);
                minMoney += C * NowP;
                NowP = Ds[i - 1][1];
                Flag_N = i - 1;
                if (NowP > Ds[i][1])
                {
                    minMoney += ((Ds[i][0] - NowD) / D2) * NowP;
                    NowD = Ds[i][0];
                    NowP = Ds[i][1];
                    Flag_N = i;
                }
            }
            else if(NowP > Ds[i][1])
            {
                minMoney += ((Ds[i][0] - NowD) / D2) * NowP;
                NowD = Ds[i][0];
                NowP = Ds[i][1];
                Flag_N = i;
            }
        }
        if (isAble)
        {
            cout << fixed << setprecision(2) << minMoney;
        }
        return 0;
    }
    
    
    
    
  • 0
    @ 2017-02-04 19:21:34
    #include <cstdio>
    #include <algorithm>
    #include <limits>
    using namespace std;
    
    int n,v=0;
    double l,c,x,b=0,cost=0;
    
    struct o_s
    {
        int v;
        double d,p;
    }o[1000];
    
    bool cmp_o_s(o_s a,o_s b)
    {
        return a.d<b.d;
    }
    
    int main()
    {
        o[0].d=0;
        scanf("%lf%lf%lf%lf%d",&l,&c,&x,&o[0].p,&n);
        for (int i=1;i<=n;i++)
            scanf("%lf%lf",&o[i].d,&o[i].p);
        n++;
        o[n].d=l;
        o[n].p=(numeric_limits<double>::min)();
        sort(o+1,o+n+1,cmp_o_s);
        while (v<n)
        {
            if (o[v].d+c*x<o[v+1].d)
            {
                printf("%d\n",-1);
                return 0;
            }
            o_s ch;
            ch.p=(numeric_limits<double>::max)();
            for (int i=v+1;i<=n;i++)
                if (o[v].d+c*x>=o[i].d)
                {
                    if ((ch.p>o[i].p&&i<n)||(ch.p>o[v].p&&i==n))
                    {
                        ch.p=o[i].p;
                        ch.d=o[i].d;
                        ch.v=i;
                    }
                }
                else
                    break;
            if (ch.p>o[v].p)
            {
                cost+=(c-b)*o[v].p;
                b=c;
            }
            else if (o[v].d+b*x<ch.d)
            {
                cost+=((ch.d-o[v].d)/x-b)*o[v].p;
                b=(ch.d-o[v].d)/x;
            }
            b-=(ch.d-o[v].d)/x;
            v=ch.v;
        }
        printf("%.2lf\n",cost);
    }
    
  • 0
    @ 2017-01-22 15:36:15
    //Copyright (C) 2017 Elsanna
    //License:GPL
    //Author:Elsanna
    
    #include <string.h>
    #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <iomanip>
    using namespace std;
    
    //Summary:
    //  在开始前,进行判断,能不能到达最近的加油站,如果不行,No solution
    //  在当前节点开始往后搜索,如果后面的节点没有比当前结点的单价便宜的,就在当前结点加满油,到达能到达的最便宜的节点那
    //      如果有比当前结点便宜的,那么就在当前结点加有加到刚刚好能到那个油站
    //          要求到里离当前结点最近的,比当前结点便宜的
    int main() {
        //Init
    
        //
        double distance_tmp, capacity, dis_per_liter, price[101];
        int n_station;
        cin >> distance_tmp >> capacity >> dis_per_liter >> price[0] >> n_station;
        double distance[101];
        distance[0] = 0;
        distance[n_station + 1] = distance_tmp;
    
        for (int i = 1; i <= n_station; i++) {
            cin >> distance[i] >> price[i];
        }
        double usage = 0.0;
    
        //left_oil_capacity放错位置进行初始化了
        double left_oil_capacity = 0.0;
    
        for (int current_pos = 0; current_pos <= n_station;) {
    
            //最近的站台都到不了
            if (capacity*dis_per_liter < distance[current_pos + 1] - distance[current_pos]) {
                cout << "No Solution" << endl;
                return 0;
            }
            double min_price_forward = 0xffff;
            
            int min_price_forward_station = current_pos + 1;
            bool found_less_price = false;
            for (int next_pos = current_pos + 1; next_pos <= n_station + 1; next_pos++) {
                //保证能到下一个节点,否则就跳出
                if (capacity*dis_per_liter < distance[next_pos] - distance[current_pos]) {
                    break;
                }
    
                //更新最近更便宜的节点
                if (price[next_pos] < min_price_forward) {
                    min_price_forward = price[next_pos];
                    min_price_forward_station = next_pos;
                    //如果有比当前结点便宜的或者相等的
                    if (price[next_pos] <= price[current_pos]) {
                        //加到刚刚好即可
                        usage += ((distance[next_pos] - distance[current_pos]) / dis_per_liter - left_oil_capacity)*price[current_pos];
                        left_oil_capacity = 0;
    
                        //到更便宜的节点那
    
                        //found_less_price便于判断是否找到了更少油价的节点
                        found_less_price = true;
                        current_pos = next_pos;
                        break;
                    }
                }
                if (next_pos == n_station + 1) {
                    //未来节点没有一个比当前结点便宜的
                    //并且终点可以直接到达
                    //那么直接加到刚刚够到达的容量即可
                    if (min_price_forward > price[current_pos]) {
                        //这一部分要用等宽字体来看
                        //↓使用费用                 两点距离↓                                       减去还留下的油↓            单价↓
                        usage += ((distance[next_pos] - distance[current_pos]) / dis_per_liter - left_oil_capacity)*price[current_pos];
                        //到达终点
    
                        cout << setiosflags(ios::fixed) << setprecision(2) << usage << endl;
                        //system("pause");
                        return 0;
                    }
                }
            }
            if (found_less_price)continue;
    
            
            //对于没有的比当前结点便宜的,就加满,到最便宜的下一个节点
            usage += (capacity - left_oil_capacity)*price[current_pos];
            left_oil_capacity = capacity - (distance[min_price_forward_station] - distance[current_pos]) / dis_per_liter;
            
    
            current_pos = min_price_forward_station;
        }
        cout << setiosflags(ios::fixed) << setprecision(2) << usage << endl;
    
        return 0;
    }
    
    • @ 2017-01-22 15:38:35

      Elsanna也是我。。。
      Author忘改了

  • 0
    @ 2016-09-08 09:10:23

    真的是自己作死,把数据范围看大了,加了个优先队列写出了个无比丑陋的代码,调的想吐血。。。
    ```#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<queue>
    #include<map>
    using namespace std;

    const int INF = 1000000000;
    const int maxn = 100 + 10;

    int n;
    double d1, C, d2, p_start, p, c;

    struct Stand {
    double d, p;
    Stand (double d, double p) : d(d), p(p) {}
    bool operator < (const Stand &rhs) const {
    return (p > rhs.p) || (p == rhs.p && d > rhs.d);
    }
    };

    int main ()
    {
    // freopen("in.txt", "r", stdin);
    cin >> d1 >> C >> d2 >> p_start >> n;

    priority_queue<Stand> Q;
    for (int i = 0; i < n; i++) {
    double tmpd, tmpp;
    cin >> tmpd >> tmpp;
    Q.push(Stand(tmpd, tmpp));
    }

    double cur = 0.000, ans = 0.000, c = 0.000;
    p = p_start;
    map<Stand, int> vis;
    int T = 1;
    bool solved = false;
    while (!solved && !Q.empty()) {
    Stand s = Q.top(); Q.pop();
    if (vis[s] == T) { cout << "-1\n"; return 0;}
    if (s.d - cur > C * d2) { Q.push(s); vis[s] = T; continue;}
    if (s.p >= p) {
    if ((d1-cur)/d2 <= C) { ans += (d1-cur)*p/d2; solved = true; continue;}
    else { ans += (C-c)*p; c = C - (s.d-cur)/d2; cur = s.d; p = s.p; T++; break;}
    }
    cur = s.d;
    ans += s.d * p / d2;
    p = s.p;
    T++;
    break;
    }

    while (!Q.empty() && !solved) {
    Stand s = Q.top(); Q.pop();
    if (vis[s] == T) { cout << "-1\n"; return 0;}
    if (cur >= s.d) continue;
    if (s.d - cur > C * d2) { Q.push(s); vis[s] = T; continue;}
    if (s.p >= p) {
    if ((d1-cur)/d2 <= C) { ans += max(0.0, (d1-cur)/d2-c) * p; solved = true; continue;}
    else { ans += (C-c)*p; c = C - (s.d-cur)/d2; cur = s.d; p = s.p; T++; continue;}
    }

    ans += max(0.0, (s.d - cur) / d2 - c) * p;
    c = 0;
    cur = s.d;
    p = s.p;
    T++;
    }
    if (!solved) {
    if ((d1-cur)/d2 > C) { cout << "-1\n"; return 0;}
    else ans += max(0.0, (d1-cur)/d2-c) * p;
    }
    printf("%.2f\n", ans);
    return 0;
    }
    ```

  • 0
    @ 2015-01-06 20:01:09

    ####评测结果

    ##__编译成功__##

    测试数据 #0: Accepted, time = 0 ms, mem = 2040 KiB, score = 20

    测试数据 #1: Accepted, time = 0 ms, mem = 2040 KiB, score = 20

    测试数据 #2: Accepted, time = 0 ms, mem = 2040 KiB, score = 20

    测试数据 #3: Accepted, time = 0 ms, mem = 2040 KiB, score = 20

    测试数据 #4: Accepted, time = 0 ms, mem = 2044 KiB, score = 20

    ##__Accepted, time = 0 ms, mem = 2044 KiB, score = 100__##

  • 0
    @ 2014-11-03 22:42:32

    分治或贪心或DP

  • 0
    @ 2013-10-24 17:14:11

    type
    ppp=record
    l,v:extended;
    end;
    type
    qqq=record
    fe,o:extended;
    end;

    var
    i,j,k,l,m,n,pop,lol:longint;
    d1,d2,p,w1,q,c,nc,max,oil,ans:extended; {浪费是种好习惯..}
    a:array[0..1000]of ppp; {浪费是种好习惯..}
    f:array[0..1000]of extended; {浪费是种好习惯..}
    z:array[0..1000]of qqq; {浪费是种好习惯..}
    begin
    read(d1,c,d2,p,n);
    for i:=1 to n do read(a[i].l,a[i].v);
    a[n+1].l:=d1; {设界...}

    for i:=n+1 downto 1 do
    begin
    a[i].l:=(a[i].l-a[i-1].l)/d2; {a[i].l变为走一段路要用的油...}
    if a[i].l >c then begin writeln(-1); halt;end;{妥妥的无解..}
    end;

    f[1]:=p*c;{初始..}
    lol:=0;

    if a[1].v<p then begin inc(lol);
    z[1].o:=c;
    z[1].fe:=a[1].v;
    f[1]:=p*a[1].l+c*a[1].v
    end
    else
    begin
    inc(lol);
    z[1].o:=c-a[1].l;
    z[1].fe:=p;
    inc(lol);
    z[2].o:=a[1].l;
    z[2].fe:=a[1].v;
    f[1]:=f[1]+a[1].v*a[1].l;
    end;

    {处理第一个...}

    for i:=2 to n+1 do
    begin
    f[i]:=f[i-1];{先传承..}
    k:=1;
    oil:=a[i].l;{耗掉的油..}
    while oil>0 do if oil<z[k].o then begin z[k].o:=z[k].o-oil;oil:=0;end
    else begin oil:=oil-z[k].o; z[k].o:=0;inc(k); end;{用掉当前最便宜同时也是放置时间最长的油..>..<,其实好像看完
    后面的时候...有个单调对列...}
    lol:=lol-k+1;{队内向前..}
    for j:=1 to lol do begin z[j].fe:=z[j+k-1].fe; z[j].o:=z[j+k-1].o;end;{队内向前..}
    lol:=lol+1;
    z[lol].fe:=a[i].v;
    z[lol].o:=a[i].l;{新人入队!}
    f[i]:=a[i].l*a[i].v+f[i];{重新装满...}
    k:=lol;

    for j:=lol-1 downto 1 do{从后爆它..}
    begin
    if z[j+1].fe<=z[j].fe then begin
    f[i]:=f[i]-(z[j].fe-z[j+1].fe)*z[j].o;{把以前的贵油倒掉...换便宜的..>。< }
    z[j].fe:=z[j+1].fe; {传!}
    z[j].o:=z[j+1].o+z[j].o; {再传!}
    k:=k-1;
    z[j+1].fe:=0;
    z[j+1].o:=0; {出对...队长-1..}
    end;
    end; {入队处理..保持单调>3< .}
    lol:=k;
    end;

    //for i:=1 to lol do
    //f[n+1]:=f[n+1]-z[i].fe*z[i].o;{到了最后一个点...出栈...嘛,其实不用这一步的...因为a[n+1].v=0,在循环时爆的时候已经把以前的都踢走了...}
    writeln(f[n+1]:0:2);{精确两位..}
    end.
    {啦啦啦啦啦...}

  • 0
    @ 2013-08-31 10:42:10

    var
    dis,c,m,l,ans,t:real;
    n,i,j:longint;
    over,x,p,d:array[0..1000] of real;
    begin
    readln(dis,c,m,p[0],n);
    l:=c*m;
    for i:=1 to n do
    readln(d[i],p[i]);
    d[n+1]:=dis;
    for i:=1 to n+1 do
    if d[i]-d[i-1]>l then begin writeln('-1'); exit end;
    i:=0;
    repeat
    for j:=i+1 to n+2 do
    if (d[j]-d[i]<=l) and (p[j]<p[i]) then break;
    t:=(d[j]-d[i])/m;
    if j<>n+2 then
    begin
    if over[i]>=t then
    over[j]:=over[i]-t
    else
    x[i]:=t-over[i]
    end
    else begin x[i]:=c-over[i]; j:=i+1; over[j]:=c-(d[j]-d[i])/m; end;
    i:=j;
    until i=n+1;
    for i:=0 to n do
    ans:=ans+p[i]*x[i];
    writeln(ans:0:2);
    end.

  • 0
    @ 2012-08-21 16:59:38

    要有一个变量记录当前油量剩余啊!第四个点啊!

  • 0
    @ 2012-07-28 11:24:16

    测试数据 02:答案错误...程序输出比正确答案长 谁能告诉我为什么???

  • 0
    @ 2012-07-25 10:31:17

    在做这道题的时候千万不要觉得烦,一定要冷静仔细地分析~!!!

    这是一道很经典的贪心:

    下一个加油站只可能有3种可能:

    1 比前一个加油站便宜 做法:在前一个加油站只需补充足够去下一个加油站的油量

    2 与前一个加油站同价钱 做法:同上

    3 比前一个加油站昂贵 做法:在前一个加油站加满油,然后去到下一个的加油站的 与前一个加油站的价格是最相近的

    这样贪心去做,但大家要有足够的耐心

    (本人调试很久呢-_-.! TAT)

    首次贴一下我的代码

    var

    dest,c,dy,pay,cy:real; {输入的第一行信息}

    dis,p:array[-1..100] of real; {dis[i],p[i]描述第i个加油站的信息}

    ans,t,d,min:real;

    i,j,k,l,m,n:longint;

    procedure init;

    begin

    readln(dest,c,dy,pay,n);

    for i:=1 to n do readln(dis[i],p[i]);

    p[0]:=pay;

    end;

    begin

    init;

    d:=0; {旅行家的位置}

    cy:=0; {库存油量}

    ans:=0; {花费}

    i:=0;

    while d=dest) then

    {如果旅行家已经去到最后一个加油,那直接去到终点}

    begin

    ans:=ans+(dest-dis[i]-cy*dy)/dy*p[i];

    d:=dest;

    break;

    end;

    j:=i+1;

    if (d+dy*c=dis[j]) and (j

  • 0
    @ 2010-07-17 09:59:13

    var

    d1,c,d2,p:real;

    n:longint;

    w,di,pi:array[0..100]of real;

    procedure init;

    var

    i:longint;

    begin

    readln(d1,c,d2,p,n);

    fillchar(di,sizeof(di),0);

    fillchar(pi,sizeof(pi),0);

    for i:=1 to n do

    readln(di[i],pi[i]);

    di[0]:=0;

    pi[0]:=p;

    di[n+1]:=d1;

    // pi[n+1]:=maxlongint;

    end;

    procedure work;

    var

    i,j,m:longint;

    x,box,money,min:real;

    begin

    fillchar(w,sizeof(w),0);

    money:=c*p;

    box:=c;

    w[0]:=c;

    for i:=1 to n+1 do begin

    box:=box-(di[i]-di)/d2;

    if box0 do begin

    min:=maxlongint;

    for j:=0 to i-1 do

    if (w[j]>0)and(pi[j]pi[i]) then begin

    w[i]:=w[i]+w[j];

    money:=money-(pi[j]-pi[i])*w[j];

    w[j]:=0;

    end;

    // writeln(money:0:2);

    w[i]:=w[i]+(c-box);

    money:=money+(c-box)*pi[i];

    // writeln(money:0:2);

    box:=c;

    end;

    writeln(money:0:2);

    end;

    begin

    init;

    work;

    end.

    山路十八弯的程序

  • 0
    @ 2009-11-07 15:16:46

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    不看题害死人啊,忘记输出-1,还好及时发现…………

  • 0
    @ 2009-11-04 23:51:04

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案错误...

     ├ Hint: Sorry, Wrong Answer! 

    ├ 测试数据 04:答案错误...

     ├ Hint: Sorry, Wrong Answer! 

    ├ 测试数据 05:答案错误...

     ├ Hint: Sorry, Wrong Answer! 

    第一次提交,输入打错了,同一行是一个距离,一个油价......

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案错误...

     ├ Hint: Sorry, Wrong Answer! 

    ├ 测试数据 05:答案正确... 0ms

    再错一次,震惊之中......

    as 终于是 ac 了

    但方法很违心,我认为这道题的数据以及楼下一些人的题解都存在问题,决策并不周全

    这是我的原版程序:

    program lyc;

    var d1,c,d2,p0,ans:real;

    n:integer;

    d,p:array[0..101] of real;

    procedure init;

    var i:integer;

    begin

    readln(d1,c,d2,p0,n);

    d[0]:=0;d[n+1]:=d1;p[0]:=p0;

    for i:=1 to n do readln(d[i],p[i]);

    end;

    procedure tan;

    var min1,min2:longint;

    need,rest,cost:real;

    i,j,k:longint;

    begin

    rest:=0;cost:=0;k:=0;

    repeat

    j:=k;min1:=0;min2:=0;

    while (j

  • 0
    @ 2009-11-04 20:48:35

    第一次做这道题,还快排了一下,感觉数据真的很弱……

    var

    a,d,f:array[0..100]of real;

    i,j,k,l,n:longint;

    d1,c,d2,p,num,len,max:real;

    procedure qsort(l,h:longint);

    var

    i,j:longint;

    x,te:real;

    begin

    i:=l;

    j:=h;

    x:=a[(i+j) div 2];

    repeat

    while a[i]x do dec(j);

    if ij;

    if il then qsort(l,j);

    end;

    begin

    readln(d1,c,d2,p,n);

    len:=c*d2;

    for i:=1 to n do

    begin

    readln(a[i],d[i]);

    if (d[i]-d)>len then begin writeln('-1'); halt; end;

    end;

    qsort(1,n);

    a[0]:=0;

    d[0]:=p;

    inc(n);

    a[n]:=d1;

    d[n]:=0;

    i:=0;

    l:=0;

    repeat

    num:=100000;

    j:=i+1;

    while (a[j]-a[i]

  • 0
    @ 2009-10-30 13:05:12

    经典的贪心思想。。。。

    最大的感受:

    写贪心程序时,如果对自己的概括,归纳能力不是很自信,不妨多分一些情况考虑(尽管有的情况可能可以用精辟的语句归为一类),虽然程序写的丑了点,但是AC才是王道!!!

信息

ID
1253
难度
6
分类
贪心 点击显示
标签
递交数
3363
已通过
807
通过率
24%
被复制
16
上传者