题目分析

我们需要在满足以下约束条件下，最小化 $T$（所有成员心情好时的总时间）：

1. 每位成员至少跑 $d$ 米：$\forall i, x_i \geq d$。
2. 总跑步距离等于 $L$ 米：$\sum_{i=1}^{n} x_i = L$。
3. 所有成员心情差时的总时间 $S \leq W$：$\sum_{i=1}^{n} s_i x_i \leq W$。

目标是最小化 $T = \sum_{i=1}^{n} t_i x_i$。

解题思路

1. 检查可行性

首先检查是否存在可行解：

• 每位成员至少跑 $d$ 米，因此最小总距离为 $n \times d$。
  • 如果 $n \times d > L$，则无解，输出 "No solution"。
• 所有成员心情差时跑最少距离的总时间 $S_{\text{min}} = \sum_{i=1}^{n} s_i d$。
  • 如果 $S_{\text{min}} > W$，则无解，因为即使跑最少距离也无法满足 $S \leq W$。

2. 贪心策略

在满足约束的条件下，为了使 $T$ 最小，应该：

• 优先让 $t_i$ 较小的成员跑更多距离（因为他们的单位时间贡献更小）。
• 让 $s_i$ 较大的成员跑最少距离 $d$（因为他们的单位时间贡献更大，会使得 $S$ 增长更快）。

具体步骤：

1. 初始化：
   • 每位成员先分配 $d$ 米，剩余距离 $L' = L - n \times d$。
   • 计算当前 $S = \sum_{i=1}^{n} s_i d$。
   • 如果 $S > W$，无解。
2. 分配剩余距离：
   • 按照 $(s_i, t_i)$ 的优先级排序：
     • 先按 $t_i$ 升序（优先让 $t_i$ 小的跑更多）。
     • 如果 $t_i$ 相同，则按 $s_i$ 降序（优先让 $s_i$ 大的跑更少）。
   • 对于每个成员，尽量分配尽可能多的剩余距离，同时保证 $S \leq W$：
     • 对于成员 $i$，最多能分配 $\Delta x_i = \min \left( \frac{W - S}{s_i}, L' \right)$。
     • 更新 $S \leftarrow S + s_i \Delta x_i$，$T \leftarrow T + t_i \Delta x_i$，$L' \leftarrow L' - \Delta x_i$。
3. 检查是否分配完所有剩余距离：
   • 如果 $L' > 0$，说明无法满足 $S \leq W$，无解。
   • 否则，返回 $T$。

代码实现（C++）

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 10007;
const double eps = 1e-6;
int n,d;
double L,W;
inline int sig(double x) { return (x>eps)-(x<-eps); }
// Si:x , Ti:y
struct point {
	double x,y;
	point(int _x=0,int _y=0) : x(_x),y(_y) {}
	bool operator < (const point &tt) const {
		return sig(x-tt.x)<0 || sig(x-tt.x)==0 && sig(y-tt.y)<0;
	}
	point operator - (const point &tt) const { return point(x-tt.x,y-tt.y); }
}dot[N],con[N];
inline double cross(point a,point b) { return a.x*b.y-a.y*b.x; }
int set_convex(point *dot,int n) {
	int top = 0;
	if (n==0) return 0;
	con[top++] = dot[0];
	if (n==1) return 1;
	con[top++] = dot[1];
	for (int i = 2; i < n; i ++) {
		while (top>=2 && sig(cross(con[top-1]-con[top-2],dot[i]-con[top-2]))<=0) top --;
		con[top++] = dot[i];
	}
	return top;
}
double ternary(point a,int l,int r) {
	double slop = 1e30;
	while (l<=r) {
		int lfd = (2*l+r)/3;
		int rfd = (l+2*r)/3;
		double ll = (a.y-con[lfd].y)/(a.x-con[lfd].x);
		double rr = (a.y-con[rfd].y)/(a.x-con[rfd].x);
		if (sig(ll-rr)>=0) {
			l = lfd+1;
			slop = min(slop,rr);
		} else {
			r = rfd-1;
			slop = min(slop,ll);
		}
	}
	return a.y*L+(W-a.x*L)*slop;
}
double work() {
	double ret = 1e30;
	if (sig(W)<0 || sig(L)<0) return -1;
	sort(dot,dot+n);
	int j = 1;
	for (int i = 0; i < n; i ++) {
		if (sig(dot[i].y-dot[j-1].y)>=0) continue;
		dot[j++] = dot[i];
	}
	n = j;
	if (sig(W-L*dot[0].x)<0) return -1;
	if (n==1) return L*dot[0].y;
	for (j = 0; j<n && sig(W-L*dot[j].x)>=0; j ++);
	int tot = j;
	int sz = set_convex(dot+j,n-j);
	for (int i = 0; i < tot; i ++) {
		ret = min(ret,L*dot[i].y);
		ret = min(ret,ternary(dot[i],0,sz-1));
	}
	return ret;
}
int main() {
	int cas;
	scanf("%d",&cas);
	while (cas--) {
		scanf("%d%d%lf%lf",&n,&d,&L,&W);
		double base = 0;
		for (int i = 0; i < n; i ++) {
			int a,b;
			scanf("%d%d",&a,&b);
			dot[i].x = a;
			dot[i].y = b;
			W -= dot[i].x*d;
			L -= d;
			base += dot[i].y*d;
		}
		double ans = work();
		if (sig(ans)<0) puts("No solution");
		else printf("%.2f\n",ans+base);
	}
	return 0;
}