比赛 |
贪心题目练习 |
评测结果 |
AAAA |
题目名称 |
旅行家的预算 |
最终得分 |
100 |
用户昵称 |
OTTF |
运行时间 |
0.011 s |
代码语言 |
C++ |
内存使用 |
3.60 MiB |
提交时间 |
2025-03-22 08:52:51 |
显示代码纯文本
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <utility>
using namespace std;
double d1;
double c;
double d2;
int n;
pair<double, double> num[11];
double res;
int main () {
freopen ("lyuxing.in", "r", stdin);
freopen ("lyuxing.out", "w", stdout);
cin >> d1 >> c >> d2 >> num[0].second >> n;
num[n + 1].first = d1;
for (int i = 1; i <= n; i++) {
cin >> num[i].first >> num[i].second;
}
sort (num + 1, num + n + 1);
int i = 0;
double oil = 0;
while (true) {
if (i == n + 1) {
break;
}
for (int j = i + 1; j <= n + 1; j++) {
if (num[j].second < num[i].second) {
if ((num[j].first - num[i].first) / d2 < c) {
res += ((num[j].first - num[i].first) / d2 - oil) * num[i].second;
oil = 0;
i = j;
goto end;
}
}
}
if (num[i + 1].first - num[i].first > c * d2) {
cout << "No Solution" << endl;
return 0;
}
res += (c - oil) * num[i].second;
oil = c;
for (int j = i + 1; j <= n + 1; j++) {
if (num[j].first - num[i].first <= oil * d2) {
oil -= (num[j].first - num[i].first) / d2;
i = j;
}
else {
break;
}
}
end:;
}
printf ("%.2lf", res);
return 0;
}