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;
}