连续变量 + 贪心

一、先把题目翻译成人话

有 (n) 种原料：

第 (i) 种有 (v_i) 升
每升含糖 (s_i) 克
可以使用其中任意 (k_i) 升
0≤ki​≤vi​

最终饮料的甜度：

$$\frac{\sum k_i s_i}{\sum k_i}=t$$

我们希望：

甜度刚好等于 (t)，同时总容量尽可能大。

二、最关键的一个变形

甜度等于 (t)：

$$\frac{\sum k_i s_i}{\sum k_i}=t$$

两边乘上分母：

$$\sum k_i s_i=t\sum k_i$$

移到一起：

$$\sum k_i(s_i-t)=0$$

这个式子非常重要。

我们可以把：

$$s_i-t$$

理解成：

第 (i) 种原料相对于目标甜度 (t)，高了多少或者低了多少。

例如目标甜度：

$$t=2$$

那么：

原料甜度	<>s_i-t<>	意义
1	-1	太甜度低
2	0	正好
5	+3	太甜
0	-2	太淡

三、为什么要“先全部使用”？

我们最终要求的是：

最大容量

所以我们可以先假设：

所有原料全部加入。

假设全部加入后，甜度不是 (t)。

这时候我们只需要：

从里面减少一些原料，使甜度恰好变成 (t)。

这样问题就简单了。

四、情况一：全部使用后，甜度太高

假设：

$$\text{当前甜度}>t$$

说明饮料太甜了。

我们需要减少一些原料。

这时候应该优先减少什么？

当然是：

甜度最高的原料。

而且不是简单地按照 (s_i) 最大，而是看：

$$s_i-t$$

也就是它比目标甜度高多少。

例如目标是 2：

甜度 3 的原料，每减少 1 升，可以减少 1 的“超出量”
甜度 5 的原料，每减少 1 升，可以减少 3 的“超出量”
甜度 10 的原料，每减少 1 升，可以减少 8 的“超出量”

所以应该：

按照 (s_i-t) 从大到小删除原料。

这其实就是一个分数背包式的贪心。

五、情况二：全部使用后，甜度太低

如果：

$$\text{当前甜度}<t$$

说明饮料太淡。

那么应该减少什么？

减少甜度最低的原料。

例如 (t=2)：

甜度 1：每减少 1 升，可以让平均甜度提高一些
甜度 0：每减少 1 升，可以让平均甜度提高更多

所以按照：

$$t-s_i$$

从大到小删除。

也就是：

优先删除离目标甜度最远的低甜度原料。

六、样例分析

输入：
4 2
6 1
5 2
8 5
1 0

目标甜度：

$$t=2$$

全部使用：

原料	容量	甜度	糖
1	6	1	6
2	5	2	10
3	8	5	40
4	1	0	0

总容量：

$$6+5+8+1=20$$

总糖：

$$6+10+40=56$$

全部使用时甜度：

$$56/20=2.8$$

太甜了。

现在需要减少“超出的糖度”

计算：

$$s_i-t$$

得到：

原料	<>s_i-t<>
1	-1
2	0
3	3
4	-2

我们需要降低甜度，所以优先删除：
甜度 5 的原料

它每减少 1 升，相当于减少：

$$5-2=3$$

的超出量。

全部使用时：

\sum v_i(s_i-t) $$ $$ =6(1-2)+5(2-2)+8(5-2)+1(0-2) $$ $$ =-6+0+24-2=16

所以需要减少 16 的“超出量”。

甜度为 5 的原料每升贡献 3：

$$16\div3=5.333333...$$

所以从 8 升甜度为 5 的原料中减少：

$$5.333333...$$

剩下：

20−5.333333=14.666667

因此答案：

14.667

和样例一致。

七、什么时候无解？

如果目标甜度 (t) 比所有原料的甜度都高：

t > 所有 s[i]

显然不可能调出这么甜的饮料。

同理：

t < 所有 s[i]

也不可能。

所以：

$$t<\min s_i$$

或者

$$t>\max s_i$$

直接输出：

0

#include <bits/stdc++.h>
using namespace std;

struct Node {
    double v;
    double s;
};

bool cmp(Node a, Node b) {
    return a.s > b.s;
}

int main() {
    int n;
    double t;

    cin >> n >> t;

    Node a[100005];

    double totalV = 0;
    double totalS = 0;

    double minS = 1e18;
    double maxS = -1e18;

    for (int i = 0; i < n; i++) {
        cin >> a[i].v >> a[i].s;

        totalV += a[i].v;
        totalS += a[i].v * a[i].s;

        minS = min(minS, a[i].s);
        maxS = max(maxS, a[i].s);
    }

    // 目标甜度不在所有原料甜度的范围内
    if (t < minS || t > maxS) {
        cout << "0.000";
        return 0;
    }

    // 全部使用时刚好满足要求
    if (fabs(totalS - totalV * t) < 1e-10) {
        cout << fixed << setprecision(3) << totalV;
        return 0;
    }

    // 全部使用后太甜
    if (totalS > totalV * t) {

        // 按甜度从大到小排序
        sort(a, a + n, cmp);

        double need = totalS - totalV * t;

        for (int i = 0; i < n; i++) {

            if (a[i].s <= t) {
                break;
            }

            // 这一种原料全部删掉可以减少多少“超出量”
            double can = a[i].v * (a[i].s - t);

            if (can <= need) {
                // 全部删掉
                totalV -= a[i].v;
                need -= can;
            } else {
                // 只需要删掉一部分
                double x = need / (a[i].s - t);
                totalV -= x;
                need = 0;
                break;
            }
        }
    }

    // 全部使用后太淡
    else {

        // 按甜度从小到大排序
        sort(a, a + n, [](Node x, Node y) {
            return x.s < y.s;
        });

        double need = totalV * t - totalS;

        for (int i = 0; i < n; i++) {

            if (a[i].s >= t) {
                break;
            }

            double can = a[i].v * (t - a[i].s);

            if (can <= need) {
                // 全部删掉
                totalV -= a[i].v;
                need -= can;
            } else {
                // 只删一部分
                double x = need / (t - a[i].s);
                totalV -= x;
                need = 0;
                break;
            }
        }
    }

    cout << fixed << setprecision(3) << totalV;

    return 0;
}

九、如果想用最容易理解的方法

这道题你只需要记住一句话：

先把所有原料都加进去，然后为了把甜度拉回 (t)，优先扔掉“离 (t) 最远”的原料。

具体来说：

全部加入后太甜
优先扔掉甜度高的
全部加入后太淡
优先扔掉甜度低的
每次为什么选“最极端”的？

因为我们希望：

扔掉尽可能少的体积，却让甜度尽快回到 t。

这就是贪心的核心。

复杂度

排序需要：

$$O(n\log n)$$

之后扫描一次：

$$O(n)$$

所以总复杂度：

$$\boxed{O(n\log n)}$$

空间复杂度：

$$\boxed{O(n)}$$

这道题最值得掌握的知识点其实是“连续变量 + 贪心”。 因为 (k_i) 可以取小数，所以最后通常会出现“某一种原料只取一部分”的情况，这也是为什么普通的 0/1 背包思路不适合这道题。

方案二:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3+10;
int n,t;
double ans;
//保存每种原料的存量和糖分 
struct node{
	int v,s;
}a[N];
bool cmp(node x, node y){
	return x.s < y.s;
}
int main(){
	cin >> n >> t;
	for(int i = 1; i <= n; i++){
		cin >> a[i].v >> a[i].s;
	}
	/*调甜度就两种方法：
	1、先用糖分高的，再用糖分低的去稀释
	2、先用糖分低的，再用糖分高的去加浓 
	*/ 
	sort(a+1,a+n+1,cmp);//糖分从低到高排序
	//先用糖分高的，再用糖分低的去稀释
	double sums = 0;//当前总糖分
	double sumv = 0;//当前总体积 
	for(int i = 1; i <= n; i++){
		int v = a[i].v, s = a[i].s; 
		//加入第i种原料后甜度超了 
		if(sums+s*v > t*(sumv+v)){
			//第i种原料不能全部加
			//把应该加的体积求出来
			double k = (t*sumv-sums)/(s-t);
			ans = max(ans,sumv+k);
			break;
		} 
		sums += s*v;
		sumv += v;
	}
	//取完甜度刚好等于t，更新答案 
	if(sums/sumv == t){
		ans = max(ans,sumv);
	}
	//先用糖分低的，再用糖分高的去加浓 
	sums = 0;//当前总糖分
	sumv = 0;//当前总体积 
	for(int i = n; i >= 1; i--){
		int v = a[i].v, s = a[i].s; 
		//加入第i种原料后甜度不够了 
		if(sums+s*v < t*(sumv+v)){
			//第i种原料不能全部加
			//把应该加的体积求出来
			double k = (t*sumv-sums)/(s-t);
			ans = max(ans,sumv+k);
			break;
		} 
		sums += s*v;
		sumv += v;
	}
	//取完甜度刚好等于t，更新答案 
	if(sums/sumv == t){
		ans = max(ans,sumv);
	}
	printf("%.3f",ans);

	return 0;
}