CCF-GESP计算机学会等级考试2026年9月五级C++T2 饮品调制

P17456 [GESP202609 五级] 饮品调制

题目描述

你想调制一份甜度恰到好处的饮品给你的朋友们品尝。

有 $n$ 种原料可供用于调制饮品。第 $i$ 种原料存量有 $v_i$ 升，每升含有 $s_i$ 克糖分。你可以自由选择原料加入饮品，但每种原料的使用量不得超过其剩余存量。也就是说，假设第 $i$ 种原料选用 $k_i$ 升，应当有 $0\le k_i\le v_i$，$k_i$ 可以取 $0$ 到 $v_i$ 之间的任何数字（包括小数）。

一份甜度恰到好处的饮品需要保证甜度恰好为 $t$。最终你调制得到的饮品甜度将为 $\frac{{\sum }_{i=1}^n{k}_i\cdot s_i}{{\sum }_{i=1}^n{k}_i}$。为了让更多的朋友喝到饮品，请问最多能调制出多少升甜度恰到好处的饮品？如果无法调制出甜度恰到好处的饮品，则认为答案是 $0$。

输入格式

第一行，两个整数 $n,t$，分别表示原料种类数量，恰到好处的甜度。

接下来 $n$ 行，每行两个整数 $v_i,s_i$，分别表示第 $i$ 种原料的存量体积，每升含有的糖分质量。

输出格式

一行，一个小数，表示能调制出的甜度恰到好处的饮品最大体积，保留三位小数。

输入输出样例 #1

输入 #1

4 2
6 1
5 2
8 5
1 0

输出 #1

14.667

输入输出样例 #2

输入 #2

2 5
3 4
5 3

输出 #2

0.000

说明/提示

对于 $40\%$ 的测试点，保证 $n=2$。

对于所有测试点，保证 $1\le n\le 2000$，$0\le t\le 200$，$1\le v_i\le 100$，$0\le s_i\le 200$。

解法一

我的题解（第一人称）

题目要求选出若干原料，每种原料选取量不超过存量，使得混合饮品甜度恰好等于 $t$，并且最大化饮品总体积。
甜度公式：
$$\frac{\sum k_i{s}_i}{\sum k_i}=t$$
变形得到：$\sum k_i(s_i-t)=0$。

我的思路：

原理：最优方案一定是排序后一段连续的原料，最多只对区间左端点或者右端点的原料取一部分体积。所以不断从两端剔除原料的贪心策略成立。

带完整注释代码

#include <bits/stdc++.h>
using namespace std;
int n,t;
// 原料结构体：v存量体积，s每升糖分
struct node{
int v,s;
};
node a[2005];
double anss=0,ansv=0; // anss：总糖分，ansv：总体积
// 比较函数：按糖分s从小到大排序
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;
}
sort(a+1,a+n+1,cmp);
// 边界判断：所有原料甜度都大于t，或者全部小于t，不可能调制成功，输出0
if (a[1].s>t||a[n].s<t){
cout<<"0.000";
return 0;
}
// 初始把所有原料全部选上，计算总糖分和总体积
for(int i=1;i<=n;i++){
anss+=a[i].s*a[i].v;
ansv+=a[i].v;
}
int p=1; // p指向当前区间最左端（甜度最小）
// 如果当前混合甜度小于目标t：说明低甜原料太多，要删掉最左边低甜原料
while (anss/ansv<t){
// 如果把左端这个原料完整删掉之后，甜度仍然<=t，可以直接完整删除
if ((anss-a[p].s*a[p].v)/(ansv-a[p].v)<=t){
anss-=a[p].s*a[p].v;
ansv-=a[p].v;
p++;
}else{
// 不能完整删掉，只删除左端原料的一部分，刚好让甜度等于t，算出答案直接输出
ansv-=(ansv*t-anss)/(t-a[p].s);
cout<<fixed<<setprecision(3)<<ansv;
return 0;
}
}
p=n; // p指向当前区间最右端（甜度最大）
// 如果当前混合甜度大于目标t：说明高甜原料太多，要删掉最右边高甜原料
while (ansv>0&&anss/ansv>t){
// 如果把右端这个原料完整删掉之后，甜度仍然>=t，可以直接完整删除
if ((anss-a[p].s*a[p].v)/(ansv-a[p].v)>=t){
anss-=a[p].s*a[p].v;
ansv-=a[p].v;
p–;
} else {
// 不能完整删掉，只删除右端原料的一部分，刚好让甜度等于t，算出答案直接输出
ansv-=(ansv*t-anss)/(t-a[p].s);
cout<<fixed<<setprecision (3)<<ansv;
return 0;
}
}
// 循环结束代表当前区间甜度恰好等于t，直接输出总体积
cout<<fixed<<setprecision (3)<<ansv;
return 0;
}

解法二（前缀+后缀扫描版本）

题解

同样是这道饮品调制题，原料依旧按糖分从小到大排序。
核心性质：最优解一定是排序后的一段连续原料。
我换了一种扫描思路：

原理：

• 从左往右取连续一段：左边甜度低，右边甜度高。不断向右扩展，甜度单调上升。一旦超过目标t，答案就在这个位置。
• 如果全部前缀甜度还不够，说明我们要选取靠右侧的连续区间。从最右端向左扩展，甜度单调下降。一旦低于目标t，答案就在这个位置。

这个写法利用了排序后连续区间的甜度单调性，不需要双端循环剔除，只用两次单向扫描就可以求出最大体积。

带完整注释代码

#include <bits/stdc++.h>
using namespace std;
int n,t;
// 原料结构体：v存量体积，s每升糖分
struct node{
int v,s;
};
node a[2005];
double anss=0,ansv=0; // anss总糖分，ansv总体积
// 比较函数：按糖分s从小到大排序
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;
}
sort(a+1,a+n+1,cmp);
// 边界判断：全部原料甜度大于t，或者全部小于t，无法调制
if (a[1].s>t||a[n].s<t){
cout<<"0.000";
return 0;
}
// 从前向后依次累加原料（前缀），不断加入甜度越来越大的原料
for(int i=1;i<=n;i++){
anss+=a[i].s*a[i].v;
ansv+=a[i].v;
// 如果加入当前原料之后，混合甜度超过t
if (anss/ansv>t){
// 当前原料不能全部取，只取一部分，让甜度等于t，算出答案输出
ansv-=(ansv*t-anss)/(t-a[i].s);
cout<<fixed<<setprecision(3)<<ansv;
return 0;
}
}
// 前缀全部加完甜度刚好等于t，直接输出答案
if (anss/ansv==t){
cout<<fixed<<setprecision(3)<<ansv;
return 0;
}
// 前缀全部加完甜度仍然小于t。清空变量，从后往前累加（后缀），加入甜度越来越小的原料
anss=0,ansv=0;
for(int i=n;i>=1;i–){
anss+=a[i].s*a[i].v;
ansv+=a[i].v;
// 如果加入当前原料之后，混合甜度小于t
if (anss/ansv<t){
// 当前原料不能全部取，只取一部分，让甜度等于t，算出答案输出
ansv-=(ansv*t-anss)/(t-a[i].s);
cout<<fixed<<setprecision(3)<<ansv;
return 0;
}
}
return 0;
}

两个解法对比小结