Sugar Water 2
涉及知识点
二分答案
题意
给定两组糖水,A组糖水有N瓶,B组糖水有M瓶。A组的每瓶糖水有$A_i$克糖,$B_i$克水;同理B组的每瓶有$C_i$克糖,$D_i$克水。从两组中各挑选出一瓶糖水混合出一瓶新的糖水的组合方式共有MN种,且组合后的糖水浓度为$\frac{a_i + c_j}{a_i + b_i + c_j + d_j}$,问这MN种方式中第k浓的糖水浓度是多少(误差不小于1e-9)?
($n, m \le 5e4, 1 \le K \le N*M, 1 \le a_i, b_i, c_i, d_i \le 1e5$)
题解
不会啊,看上去是个分治,咋做捏,等着补题了
实际上是二分答案,对于每次二分的check(mid),就是要检验能配成这种浓度的组合方式是不是大于k种。这个子问题看上去必须要遍历所有组合方式,但实际上它和leetcode第一题的两数之和思想是完全一样的,可以优化到$O(nlogn)$,即我们固定某一维a[i],看a[i]这杯糖水距离配成mid浓度还需要额外添加(多余)的糖的数目,用这个去二分搜索另一维。因此总时间复杂度是$O(nlognlogp)$,p表示精度要求所需要搜索的数据范围。代码如下:
/**
* @file template.cpp
* @author Emanual20(Emanual20@foxmail.com)
* @brief For Codeforces, Atcoder or some other OJs else
* @version 0.1
* @date 2023-3-19
*
* @copyright Copyright (c) 2022
*
*/
#pragma GCC optimize(2)
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const long double eps = 1e-12;
int n, m;
ll k;
struct item{
int s, w;
};
vector<item> va, vb;
bool check(long double ck){
long double portion = ck / (1 - ck);
ll tot = 0;
vector<long double> v;
for (int i = 0; i < m; i++){
long double res = vb[i].s - vb[i].w * portion;
v.push_back(res);
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++){
long double res = va[i].s - va[i].w * portion;
tot += v.end() - lower_bound(v.begin(), v.end(), -res);
}
// cout << ck << " " << tot << endl;
return tot >= k;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
va = vector<item>(n, {0, 0}), vb = vector<item>(m, {0, 0});
for (int i = 0; i < n; i++){
cin >> va[i].s >> va[i].w;
}
for (int i = 0; i < m; i++){
cin >> vb[i].s >> vb[i].w;
}
long double l = 0, r = 1;
while(abs(l - r) > eps){
long double mid = (l + r) / 2;
if(check(mid)){
l = mid;
}
else
r = mid;
}
cout << fixed << setprecision(10) << l * 100 << endl;
return 0;
}
二分
好的,已经更新了