c - 2019-3 填还是不填(30分)我无法AC，因为我打不通 "last dist is exactly D"

Question

问题是:有了高速公路，从杭州开车到任何其他城市都很容易。但由于汽车的油箱容量有限，我们必须时不时地在途中寻找加油站。不同的加油站可能给出不同的价格。您需要仔细设计最便宜的路线。

输入规范:每个输入文件包含一个测试用例。对于每种情况，第一行包含 4 个正数:C​最大​​(≤100)， jar 体最大容量； D(≤30000)，杭州到目的城市的距离； D​平均​​ (≤20)，汽车每单位汽油可以行驶的平均距离； N (≤ 500)，加油站总数。接下来是N行，每行包含一对非负数:P​我​​ ，单位汽油价格，以及 D​我​​ (≤D)，该站到杭州的距离，i=1,⋯,N。一行中的所有数字均以空格分隔。

输出规范:对于每个测试用例，在一行中打印最便宜的价格，精确到小数点后两位。假设开始时水箱是空的。如果无法到达目的地，则打印最大行驶距离 = X，其中 X 是汽车可以行驶的最大可能距离，精确到小数点后两位。

示例输入 1:50 1300 12 86.00 12507.00 6007.00 1507.10 07.20 2007.50 4007.30 10006.85 300示例输出 1:749.17输入示例 2:50 1300 12 27.10 07.00 600示例输出 2:最大行驶距离=1200.00

我使用贪心算法来解决这个问题，首先加满油箱以到达最近且最便宜的车站，如果我们没有这样的车站，那么我们可能会到达目的地或在范围内找到更便宜的车站我们可以达到。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 500
typedef struct Station
{
    int distance;
    double price;
}Station_t;

int compare(const void *p1, const void *p2)
{
    const Station_t *pleft = (Station_t *)p1;
    const Station_t *pright = (Station_t *)p2;
    return pleft->distance < pright->distance ? -1 : pleft->distance > pright->distance;
}

int main()
{
    int capacity, totalDistance, davg, num, i;
    double usedMoney = 0;
    double usingC = 0;
    scanf("%d %d %d %d", &capacity, &totalDistance, &davg, &num);
    Station_t stas[N];
    for(i = 0; i < num; ++i)
    {
        scanf("%lf %d", &stas[i].price, &stas[i].distance);
    }
    stas[num].distance = totalDistance;
    stas[num].price = 0;
    qsort(stas, num, sizeof(Station_t), compare);
    if(stas[0].distance > 0)
    {
        printf("The maximum travel distance = 0.00");
        return 0;
    }
    Station_t *cur = stas, *next = &stas[1];
    while(cur != &stas[num - 1])
    {
        while(next->distance - cur->distance <= davg * capacity)
        {
            if(next->price < cur->price)
            {
                usedMoney += ((double)(next->distance - cur->distance - davg * usingC) / (double)davg) * cur->price;
                cur = next;
                if(cur == &stas[num - 1])
                    break;
                ++next;
            }
            else
            {
                if(next == &stas[num - 1])
                    break;
                ++next;
            }
        }
        if(cur == &stas[num - 1])
            break;
        usedMoney += (capacity - usingC) * cur->price;
        Station_t *temp = cur + 1, *fin = temp;
        while(fin != next)
        {
            if(fin->price < temp->price)
                temp = fin;
            ++fin;
        }
        usingC = capacity - (double)(temp->distance - cur->distance) / (double)davg;
        cur = temp;
    }
    if(totalDistance - cur->distance <= davg * capacity)
    {
        usedMoney += (double)(totalDistance - cur->distance) / (double)davg * cur->price;
        printf("%.2lf", usedMoney);
    }
    else
    {
        printf("The maximum travel distance = %.2f", (float)(cur->distance + davg * capacity));
    }
    return 0;
}

我无法完成名为“最后一个距离恰好是 D”的示例

Answer 1

您的比较函数有两个问题:

1) 由于参数为const ，您需要一个指向 const 的指针:

Station_t *pleft = (Station_t *)p1;

应该是

const Station_t *pleft = p1;  // There is no need to cast

2) 不够返回a > b

返回值含义:

<0 The element pointed by p1 goes before the element pointed by p2

0  The element pointed by p1 is equivalent to the element pointed by p2

>0 The element pointed by p1 goes after the element pointed by p2

你想要:

return pleft->distance < pright->distance ? -1  : pleft->distance > pright->distance;

这样就返回-1 , 0或1取决于a < b , a == b或a > b