题解：Granny的威士忌冲洗问题

题目描述

Granny需要在Ness先生到访前，通过冲洗奶油罐尽可能多地清除罐中的威士忌。她最多可以进行k次冲洗操作，每次操作包括：

1. 向罐中倒入一定量的水（可以为0）
2. 充分混合罐中液体
3. 倒出液体，使罐中剩余Vr体积的混合液体

已知条件：

• k：最大冲洗次数（1 ≤ k ≤ 100）
• Vb：桶中可用的雨水总量
• Vw：罐中初始威士忌体积
• Vr：每次倒出后罐中残留液体体积
• Vc：奶油罐的最大容量（Vc > Vw, Vr）

目标：确定最优的冲洗策略（每次使用的水量），使得最后一次冲洗后罐中残留的威士忌量最小。

解题思路

关键观察

1. 稀释原理：每次冲洗都会稀释罐中的威士忌浓度。残留的威士忌量与每次冲洗使用的水量有关。
2. 最优策略：要使最终威士忌量最小，应该尽可能多地使用水，并且尽可能早地使用大量水（因为早期冲洗的稀释效果会被后续冲洗放大）。
3. 约束条件：
   • 总用水量不超过Vb
   • 任何时候罐中液体总量不超过Vc

数学建模

1. 设第i次冲洗使用的水量为xi
2. 每次冲洗后，罐中威士忌浓度为：当前威士忌量 / (当前总液体量)
3. 倒出后，残留威士忌量为：Vr × 当前浓度

最优解性质

最优解具有以下特点：

1. 尽可能使用全部k次冲洗机会（因为更多冲洗次数能更有效地稀释）
2. 前k-1次冲洗使用尽可能少的水（刚好使罐中液体达到Vr），最后一次使用剩余所有可用水
3. 或者当k=1时，直接使用全部可用水

算法选择

1. 三分搜索：对于k>1的情况，可以三分搜索第一次冲洗的最优用水量x，使得剩余k-1次冲洗能均匀分配剩余水量(Vb-x)
2. 直接计算：对于k=1的情况，直接使用min(Vb, Vc-Vw)的水量

实现步骤

1. 检查是否可以不冲洗直接满足条件（Vr ≥ Vw）
2. 对于k=1，直接使用最大可能水量
3. 对于k>1：
   • 前k-1次冲洗每次使用y = min((Vb-x)/(k-1), Vc-Vr)水量
   • 使用三分搜索找到最优的x

代码实现

见原始C++代码，它实现了上述算法，包括：

1. 输入处理
2. 特殊情况处理（Vr ≥ Vw）
3. 三分搜索寻找最优解
4. 结果输出

复杂度分析

• 每个测试用例的时间复杂度：O(log(1/eps))，其中eps是精度要求（1e-9）
• 空间复杂度：O(1)

示例解释

样例输入：

2 15.0 25.0 1.0 50.0

解释：

• 可以进行2次冲洗，有15.0单位水可用
• 最优策略是：
  • 第一次冲洗使用0.00水（仅倒出，不稀释）
  • 第二次冲洗使用15.00水（最大可用量） 输出：

2 0.00 15.00

这个策略确保了最后一次冲洗后罐中残留的威士忌量最小。

代码实现

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ;
#define eqs 1e-9
int k ;
double vb , vw , vr , vc ;
double solve(double x) {
	double ans = vw/(vw+x) ;
	if( k > 1 ) {
		double y = min( (vb-x)/(k-1), vc-vr) ;
		for(int i = 1 ; i < k ; i++)
			ans *= vr/(vr+y) ;
	}
	return ans ;
}
int main() {
	while( scanf("%d", &k) != EOF ) {
		if(k == 0) break ;
		scanf("%lf %lf %lf %lf", &vb, &vw, &vr, &vc) ;
		if( vr-vw-vb > eqs ) {
			printf("0\n") ;
			continue ;
		}
		double low = max(0.0,vr-vw) , mid1 , mid2 , high = min(vb,vc-vw) ;
		while( low + eqs < high ) {
			mid1 = (low + high)/2.0 ;
			mid2 = (mid1 + high)/2.0 ;
			if( solve(mid1) > solve(mid2) ) {
				low = mid1 ;
			}
			else
				high = mid2 ;
		}
		printf("%d", k) ;
		printf(" %.2f", high) ;
		if( k > 1 ) high = min(vc-vr,(vb-low)/(k-1)) ;
		for(int i = 1 ; i < k ; i++) {
			printf(" %.2f", high) ;
		}
		printf("\n") ;
	}
	return 0 ;
}