题解 AT1807 【食塩水】
encore
2019-02-15 17:06:10
先说吧，这题是二分答案。~~你不知道我DP做了多久QAQ。~~
一道很有意思的二分题。我们假设最终答案为$x$。显然有 $ 0 \leq x \leq 100 $。当然你可以说$x$一定大于最小的那个浓度之类，不过无所谓，反正不差那么点时限。
然而只知道二分并没有什么卵用，解决这题还需要一个贪心策略。如果你稍微做过一会儿你就知道，并不是浓度越大越好的。
设所有盐水的集合为$S$。我们假设选取了$S_{a_1}$、$S_{a_2}$、$S_{a_3}$、……$S_{a_k}$这$k$瓶。现在我们来判断这$k$瓶盐水能不能混合出浓度大于$x\%$的盐水。很显然，新的盐水的浓度为：
$\frac{w_{a_1} p_{a_1} +w_{a_2} p_{a_2} +w_{a_3} p_{a_3} +...+w_{a_k} p_{a_k}}{w_{a_1}+w_{a_2}+w_{a_3}+...+w_{a_k}}$
。
那么只要 $\frac{w_{a_1} p_{a_1} +w_{a_2} p_{a_2} +w_{a_3} p_{a_3} +...+w_{a_k} p_{a_k}}{w_{a_1}+w_{a_2}+w_{a_3}+...+w_{a_k}} \geq x$就说明当前选取的$x$可行。
然后我们将上面的式子变形：
$w_{a_1} p_{a_1} +w_{a_2} p_{a_2} +w_{a_3} p_{a_3} +...+w_{a_k} p_{a_k} - x\times (w_{a_1} +w_{a_2}+w_{a_3}+...+w_{a_k}) \geq 0$
然后……
$w_{a_1} (p_{a_1}-x) +w_{a_2} (p_{a_2}-x) +w_{a_3} (p_{a_3}-x) +...+w_{a_k} (p_{a_k}-x) \geq 0$
好像没什么啊？但是我们可以发现，当$x$确定的时候，对于所有的$S_i$，它的$w_i (p_i - x)$ 都是确定的。选取$S_i$对应的$w_i (p_i - x)$一定是越大越好啦。所以在我们二分答案$x$的时候，只要处理出所有的$w_i (p_i - x)$，再按照$w_i (p_i - x)$的值从大到小选取盐水，就可以得到对于当前的$x$最优解。如果这个解符合，说明我们的$x$小于等于答案，如果不符合则相反。
基本差不多了，不过要注意精度之类的细节啊。下面贴AC代码：
````cpp
#include <cmath>
#include <iomanip>
#include <iostream>
#include <queue>
using namespace std;
typedef long double ld;
const int maxn = 1001, maxk = 1001;
int n, k;
ld p[maxn], w[maxn];
inline ld check(ld val) {
priority_queue<ld> v;//用来排序，vector加sort也一样的
for (register int i = 1; i <= n; ++ i) {
v.push(w[i] * (p[i] - val));
}
ld sum = 0;
for (register int i = 1; i <= k; ++ i) {
sum += v.top();
v.pop();
}
return sum;
}
int main(void) {
cin >> n >> k;
for (register int i = 1; i <= n; ++ i)
cin >> w[i] >> p[i];
ld l = 0, r = 100, mid = 1, mid_old = 0;
while (abs(mid - mid_old) >= 1e-10) { //自创沙雕二分
mid_old = mid;
mid = 0.5 * (l + r);
ld tmp = check(mid);
if (tmp > 0) l = mid;
else r = mid;
}
cout.setf(ios::fixed);
cout << setprecision(9) << mid << endl; //保留九位小数，
cout.unsetf(ios::fixed); //头文件<iomanip>
return 0;
}
````
最后给你们看看我的WA提交记录。。。
[https://www.luogu.org/recordnew/show/16347998](https://www.luogu.org/recordnew/show/16347998)
[https://www.luogu.org/recordnew/show/16348654](https://www.luogu.org/recordnew/show/16348654)