AtCoder ABC294 F - Sugar Water 2

题意

有 \(2\) 排糖和水。

第 \(1\) 排有 \(N\) 瓶糖和 \(N\) 瓶水。糖分别有 \(A_i\) 克，水分别有 \(B_i\) 克。

第 \(2\) 排有 \(M\) 瓶糖和 \(M\) 瓶水，糖分别有 \(C_i\) 克，水分别有 \(D_i\) 克。

若要从第 \(1\) 排糖水中找到 \(A_i\) 克糖和 \(B_i\) 克水，第 \(2\) 排中找到 \(C_i\) 克糖和 \(D_i\) 克水进行混合，问排名第 \(K\) 甜的糖水的含糖量是多少。

算法

二分查找 + 二分答案

实现

主函数

令 \(x\) 为糖的质量，\(y\) 为水的质量，\(t\) 为含糖量。

首先二分答案 \(t\)。

如果知道比 大于 \(t\) 的 和 小于 \(t\) 的 和 等于 \(t\) 的 各有多少种方案，那么就可以知道 \(t\) 的排名，然后根据 \(t\) 的排名调整 \(l\) 和 \(r\) 的范围。

double l = 0, r = 1;

while(r - l > 1e-14){
	double mid = (l + r) / 2;
	int x = check(mid);	// 如果以浓度 mid 为标准，浓度大于等于 mid 的有多少种。 
	if(x >= k){
		ans = mid;
		l = mid;	// 试着寻找更大值 
	}
	else{
		r = mid;	// 寻找更小值 
	}
}

check(t) 函数

check(t) 函数要求的是如果以浓度 \(t\) 为标准，浓度大于等于 \(t\) 的有多少种。

因为 \(t = \dfrac{x}{x+y}\)，所以如果知道 \(t\) 和 \(y\)，就可以知道 \(x = \dfrac{t}{1-t} \times y\)。

int check(double t){	// 如果以浓度 t 为标准，浓度大于等于 t 的有多少种。
	int res = 0;
	double r = t / (1 - t);
	
	for(int i=1; i<=m; i++){
		// v[i] 存储的是第 2 排还需要多少糖才能达到 t 浓度 
		v[i] = c[i] - d[i] * r;
//相当于v[i] = c[i] - t / (1 - t) * d[i]; 
	}
	
	sort(v+1, v+m+1);
	
	for(int i=1; i<=n; i++){
		double w = a[i] - b[i] * r;
//		相当于 w = a[i] - t / (1 - t) * b[i]; 
		res += find(-w);		// 二分找 v 数组种大于等于 -w 的有多少项 
	}
	
	return res;
}

find(x) 函数

find(x) 函数是寻找 \(v\) 数组中大于等于 \(x\) 的有多少项。

首先二分查找第 \(1\) 个大于等于 \(x\) 的值在第几个位置，设为 \(res\) 。

有了 \(res\) 后，不难发现小于 \(x\) 的有 \(x-1\) 项，那么大于等于 \(x\) 的就有 \(m - (res - 1)\) 项。

int find(double x){		// 寻找 v 数组中大于等于 x 的有多少项 
	int l = 1, r = m;
/*
	如果最终发现没有大于等于 x 的值，那么 res 如果一开始设为 0 就会得到
	返回值为 m - 0 + 1的情况。因此将 res 的初始值设为 m + 1，那么最终如
	果没有寻找到将会返回 m - (m + 1) + 1，也就是 0，这样才正确。 
*/ 
	int res = m + 1;
	while(l <= r){
		int mid = (l + r) / 2;
		double pivot = v[mid];
		if(pivot >= x){
			res = mid;
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	return m - res + 1;
//	return m -(res - 1);
}

完整代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e4 + 10;

int n, m, k, a[N], b[N], c[N], d[N]; 

double ans, l = 0, r = 1, v[N];

int find(double x){		// 寻找 v 数组中大于等于 x 的有多少项 
	int l = 1, r = m;
/*
	如果最终发现没有大于等于 x 的值，那么 res 如果一开始设为 0 就会得到
	返回值为 m - 0 + 1的情况。因此将 res 的初始值设为 m + 1，那么最终如
	果没有寻找到将会返回 m - (m + 1) + 1，也就是 0，这样才正确。 
*/ 
	int res = m + 1;
	while(l <= r){
		int mid = (l + r) / 2;
		double pivot = v[mid];
		if(pivot >= x){
			res = mid;
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	return m - res + 1;
//	return m -(res - 1);
}

int check(double t){	// 如果以浓度 t 为标准，浓度大于等于 t 的有多少种。
	int res = 0;
	double r = t / (1 - t);
	
	for(int i=1; i<=m; i++){
		// v[i] 存储的是第 2 排还需要多少糖才能达到 t 浓度 
		v[i] = c[i] - d[i] * r;
//相当于v[i] = c[i] - t / (1 - t) * d[i]; 
	}
	
	sort(v+1, v+m+1);
	
	for(int i=1; i<=n; i++){
		double w = a[i] - b[i] * r;
//		相当于 w = a[i] - t / (1 - t) * b[i]; 
		res += find(-w);		// 二分找 v 数组种大于等于 -w 的有多少项 
	}
	
	return res;
}

signed main(){
	// 读入 
	scanf("%lld %lld %lld", &n, &m, &k);
	
	for(int i=1; i<=n; i++){
		scanf("%lld %lld", a+i, b+i);
	}
	
	for(int i=1; i<=m; i++){
		scanf("%lld %lld", c+i, d+i); 
	}
	
	while(r - l > 1e-14){
		double mid = (l + r) / 2;
		int x = check(mid);	// 如果以浓度 mid 为标准，浓度大于等于 mid 的有多少种。 
		if(x >= k){
			ans = mid;
			l = mid;	// 试着寻找更大值 
		}
		else{
			r = mid;	// 寻找更小值 
		}
	}
	
	// 输出 
	printf("%.10lf", ans * 100);
	return 0;
}