AT_abc034_d [ABC034D] 食塩水 题解

AT_abc034_d [ABC034D] 食塩水

Link: https://atcoder.jp/contests/abc034/tasks/abc034_d

题目描述

有N NN( 1 ≤ N ≤ 1000 ) (1≤N≤1000)(1≤N≤1000)个装有食盐水的容器。容器从1 11到N NN标号。第i ii号容器有浓度为p i % p_i\%pi​%( 0 ≤ p i ≤ 100 ) (0≤p_i≤100)(0≤pi​≤100)的食盐水w i w_iwi​( 1 ≤ w i ≤ 10 9 ) (1≤w_i≤10^9)(1≤wi​≤109)克。高桥君需要选择K KK( 1 ≤ K ≤ 1000 ) (1≤K≤1000)(1≤K≤1000)个容器，并把选择的容器里的食盐水全部混合在一起。请你编程求出高桥君可以获得的盐水的最大浓度。

输入格式

第一行两个整数N NN、K KK；
接下来N NN行，每行两个数w i w_iwi​、p i p_ipi​。

输出格式

一行一个实数x xx，表示高桥君能得到的最大浓度的盐水浓度为x % x\%x%。

输入输出样例 #1

输入 #1

3 2 100 15 300 20 200 30

输出 #1

25.000000000

Solution

1. 题意

有n nn瓶食盐水，第i ii瓶的浓度为p i p_ipi​，质量为w i w_iwi​，从中取出k kk瓶，求混合后最大可能的浓度（质量分数）。

2. 分析

需要说明的是，本题提到的浓度从含义上存在一定的不妥。本题的浓度的准确的表述是溶质的质量分数（溶质质量与溶液质量的比值），以下全部使用“质量分数”。

首先是溶液（solution）混合后的溶质质量分数变化关系。如果将质量分别为w 1 ∼ w t w_1\sim w_tw1​∼wt​，食盐质量分数分别为p 1 ∼ p t p_1\sim p_tp1​∼pt​的溶液混合均匀，那么总体的质量分数是

P = ∑ i = 1 t w i p i ∑ i = 1 t w i × 100 % P=\dfrac{\sum_{i=1}^{t} w_ip_i}{\sum_{i=1}^{t} w_i}\times 100\%P=∑i=1t​wi​∑i=1t​wi​pi​​×100%

也即选定的这些盐水质量分数的加权平均值。权重的存在使得我们需要在“提高溶质含量”和“减小溶液质量”二者之间找到一个平衡点。因此“直接选择前k kk个最浓的盐水”是最常见的错误思路。

这题我们考虑使用二分法求解。我们设目标质量分数为p target p_\text{target}ptarget​，那么对于选定的k kk份盐水而言，每一份都会对这个目标值产生一定的贡献（contribute），如果这份盐水的质量分数高于目标，则贡献为正（因为加进去后一定会让质量分数提升），否则为负（加进去后就拖了后腿），而盐水的质量就是权重（很明显质量越大越有影响力）。

因此某一份盐水对质量分数的提升的贡献是w i ( p i − p target ) w_i(p_i-p_\text{target})wi​(pi​−ptarget​)，总体的贡献就是

∑ i = 1 k w i ( p i − p target ) \sum_{i=1}^{k}w_i(p_i-p_\text{target})i=1∑k​wi​(pi​−ptarget​)

从贪心的角度来讲，若要让总体的质量分数尽可能提高，肯定要优先选择贡献大的。将所有的盐水按照贡献由大到小排序，选出贡献值前k kk大的，如果总体的贡献大于或等于0 00，意味着可以考虑进一步提升，反之则不行。

思路上和 P1570 非常类似。

3. 代码

#include<iostream>#include<vector>#include<algorithm>#include<cmath>usingnamespacestd;classsolution{public:doubleweight;// 质量doubleconcentration;// 质量分数doublecontribute;// 贡献solution(doubleweight=0,doubleconcentration=0):weight(weight),concentration(concentration){}};boolcompare(constsolution&s1,constsolution&s2){returns1.contribute>s2.contribute;}intn,k;solution*containers;inlinedoublestatus_sum(){doubleresult=0;for(inti=1;i<=k;i++)result+=containers[i].contribute;returnresult;}boolavailable(doubletarget){for(inti=1;i<=n;i++)containers[i].contribute=(containers[i].concentration-target)*containers[i].weight;sort(containers+1,containers+n+1,compare);returnstatus_sum()>=0;}intmain(){scanf("%d%d",&n,&k);containers=newsolution[n+10];for(inti=1;i<=n;i++)scanf("%lf%lf",&containers[i].weight,&containers[i].concentration);doubleleft=0.0,right=100.0,middle=50.0;while(fabs(right-left)>=1e-11){middle=(left+right)*0.5;if(available(middle))left=middle;elseright=middle;}printf("%.10lf\n",middle);}

4. Trivia

• 常温常压（20℃，1 atm）下食盐（主要成分为 NaCl）的溶解度约为 36g/100ml。若认为 100ml 的水的质量为 100g，则常温下氯化钠溶液中氯化钠质量分数不会超过 26.5%；
• 也就是说常温状态下，样例中出现的 30% 的盐水会发生沉淀（如果这样的话也不能叫溶液了）。