【題意】：有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 }