【题意】：有n个人，第i个人在心情不好时跑一米要si秒，在心情好时跑一米要ti秒。现在有一段长为L的跑道，问你在每人至少跑d米且最坏情况用时小于等于w的情况下跑完L的跑道，最短用时为多少。
【题解】：这题正解应该是用线性规划做的，可惜我不懂。
用排序加贪心加小优化压着时间过了。
首先要贪心得出一个结论，就是每人都跑了d米之后，剩下的路程一定是由一个人或者最多两个人跑完。
以下给出证明：
假设有三个以上的人跑剩下的距离，任取其中三个人a,b,c，且sa>sb>sc.
显然我们可以得出一组x,y是关于方程 sb = x * sa + y * sc的解且x + y = 1.
然后有两种情况：
若 tb < x * ta + y * tc . 显然我们把 a 和 c所跑的路程尽可能按比例换成b跑，这样最坏情况下的时间不会变，但最好情况下的时间减少了。
同理,若 tb >= x * ta + y * tc. 我们就可以把b跑的路程尽可能换成a和c跑，这样最好情况下的时间也是减少的。
由此可得，最后一定最多只有两个人在跑剩下的距离。
然后直接枚举任意两个人就可以算出答案。
我加了点小优化就是当si<sj且ti<tj时，j这个人显然是多余的，可以直接忽略不计。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define maxn 10050
19 int n;
20 double d, l, w;
21 double ans, good;
22 struct Person {
23 double s, t;
24 bool operator <(const Person &a) const {
25 if(s != a.s) return s < a.s;
26 return t < a.t;
27 }
28 }p[maxn];
29
30 void solve() {
31 sort(p + 1, p + n + 1);
32 int tot = 1;
33 for(int i = 2; i <= n; i++) {
34 if(p[i].t < p[tot].t) p[++tot] = p[i];
35 }
36 double ans = 1e25;
37 for(int i = 1; i <= tot; i++) {
38 if(l * p[i].s > w) break;
39 ans = min(ans, good + l * p[i].t);
40 for(int j = i + 1; j <= tot; j++) {
41 double ww = l * p[j].s;
42 if(ww > w) ww = w;
43 double y = (ww - l * p[i].s) / (p[j].s - p[i].s);
44 ans = min(ans, good + y * p[j].t + (l - y) * p[i].t);
45 }
46 }
47 if(ans > 1e24) printf("No solution\n");
48 else printf("%.2f\n", ans);
49 }
50 int main() {
51 int T;
52 scanf("%d", &T);
53 while(T--) {
54 good = 0.0;
55 scanf("%d%lf%lf%lf", &n, &d, &l, &w);
56 for(int i = 1; i <= n; i++) {
57 scanf("%lf%lf", &p[i].s, &p[i].t);
58 w -= p[i].s * d;
59 good += p[i].t * d;
60 }
61 l -= d * n;
62 if(w < 0 || l < 0) {
63 printf("No solution\n");
64 continue;
65 }
66 solve();
67 }
68 return 0;
69 }