Logo Kelvin的博客

博客

“#526. 旅行家问题”的测试用例很明显是错的

2023-03-10 17:20:29 By Kelvin

2.wrong answer 1st lines differ - expected: '257.85', found: '254.61'

3.wrong answer 1st lines differ - expected: '309.58', found: '302.30'

4.wrong answer 1st lines differ - expected: '378.11', found: '376.87'

用例2.3.4.很明显都有更优解,很明显,不解释了

#include<iostream>
#include<algorithm>
#define MAX_NUM 10
#define WRONG_ANSWER_RIGHT_METHOD
//#define RIGHT_ANSWER_WRONG_METHOD
using namespace std;

struct Station {
    double dis, pri;
}sta[MAX_NUM];

double d_total, cap, d_perL, pri_min;
int N;

bool cmp(Station sta1, Station sta2) {
    return sta1.dis < sta2.dis;
}

bool Run(int now, double num_L) {
    if (now == N + 1) return true;
    double d_able = sta[now].dis + cap * d_perL;
    int next = -1, temp = -1;
    for (int i = now + 1; i <= N + 1 && sta[i].dis <= d_able; i++) {
        if (i == N + 1) temp = next == -1 ? i : next;
        if (next == -1) next = i;
        else if (sta[i].pri <= sta[next].pri) next = i;
#ifdef WRONG_ANSWER_RIGHT_METHOD
        if (sta[next].pri < sta[now].pri) {
            pri_min += ((sta[next].dis - sta[now].dis) / d_perL - num_L) * sta[now].pri;
            return Run(next, 0);
        }
#endif
    }
    if (next == -1) return false;
#ifdef RIGHT_ANSWER_WRONG_METHOD
    if (temp != -1 && sta[temp].pri < sta[now].pri) next = temp;
    if (sta[next].pri < sta[now].pri) {
        pri_min += ((sta[next].dis - sta[now].dis) / d_perL - num_L) * sta[now].pri;
        return Run(next, 0);
    }
#endif
    pri_min += (cap - num_L) * sta[now].pri;
    return Run(next, cap - (sta[next].dis - sta[now].dis) / d_perL);
}

int main() {
    cin >> d_total >> cap >> d_perL >> sta[0].pri >> N;
    for (int i = 1; i <= N; i++) cin >> sta[i].dis >> sta[i].pri;
    sort(sta, sta + N + 1, cmp);
    sta[N + 1] = {d_total, 0};
    if (Run(0, 0)) printf("%.2lf\n", pri_min);
    else printf("No Solution\n");
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。