G5026 [GESP202609 五级] 饮品调制 题解

知识点：贪心、排序、加权平均、浮点运算。

解题思路

先加入全部原料，计算高于目标的总糖差plus和低于目标的总糖差minus。仅在失衡较大的一侧删减，优先删除单位体积偏离目标最多的原料，直到糖差平衡。

为什么正确

每删一升偏差d可修正d单位失衡，优先取最大d使损失体积最小；交换任意逆序删减可不增损失，故贪心最优。

易错点

允许删去小数升，最后一种原料可只删部分；甜度恰等于目标的原料不应删，输出三位小数。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,t;
    cin>>n>>t;
    vector<pair<int,int>>neg,pos;
    double vol=0,minus=0,plus=0;
    for(int i=0;i<n;i++) {
        int v,s;
        cin>>v>>s;
        vol+=v;
        if(s<t) {
            neg.push_back({t-s,v});
            minus+=(t-s)*v;
        }
        if(s>t) {
            pos.push_back({s-t,v});
            plus+=(s-t)*v;
        }
    }
    auto a=plus>minus?pos:neg;
    double excess=abs(plus-minus);
    sort(a.rbegin(),a.rend());
    for(auto [d,v]:a) {
        double drop=min((double)v,excess/d);
        vol-=drop;
        excess-=drop*d;
    }
    cout<<fixed<<setprecision(3)<<vol;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。