自动搬运

查看原文

来自洛谷，原作者为

	CSP_Sept 私が戻ってきたのはね。 もう一度、星の音を聞くためだよ

搬运于2025-08-24 22:23:28，当前版本为作者最后更新于2020-07-10 13:48:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

子任务 1

• 暴力，挨个算出每两杯水混合后的温度，sort 一遍求 $k$ 大。
• 期望得分：$10$ 分。

子任务 2

• 贪心
• 期望得分：$40$ 分。

结论是：混合后温度最高的一杯水，混合前的两杯中必定有原先温度最高的一杯。

证明

贪心参考代码（By chenxinyang2006）：

#include <cstdio>
#include <algorithm>
#define ll long long
int n,k;
int cnt;
struct node{
	ll a,c;
}Q[1000005],now[1000005];

bool cmp(node a,node b){
	if(a.c == b.c) return a.a < b.a;
	return a.c > b.c;
}

int main(){
	scanf("%d%d",&n,&k);
	for(int i = 1;i <= n;i++){
		scanf("%lld%lld",&Q[i].a,&Q[i].c);
	}
	std::sort(Q + 1,Q + n + 1,cmp);
	double mx = 0,tmp;
	for(int i = 2;i <= n;i++){
	    tmp = (Q[1].a * Q[1].c + Q[i].a * Q[i].c) * 1.0 / (Q[1].a + Q[i].a);
		if(mx < tmp) mx = tmp;
	}
	printf("%.3f\n",mx);
	return 0;
}

---

综合以上算法，可以获得 $50$ 分。

子任务 3

• 正解
• 期望得分：$100$ 分

思路

注意到是求 $k$ 大，那么求 $k$ 大实际上只有两种方式：

1. 通过求 $1$ 大，$2$ 大，$3$ 大 …… 直到求出 $k$ 大。
2. 二分答案，然后数个数。

注意到 $k$ 是 $10^{10}$ 级别的，所以肯定选第二种了。

设当前二分的值为 $v$，那么我们要求的是数对 $(i,j)$，满足 $1 \le i < j \le n,\dfrac{a_i \times c_i + a_j \times c_j}{a_i +a_j} \ge v$ 的数量

显然，$a_i+a_j>0$，所以变形得到

$$a_i \times c_i + a_j \times c_j \ge v \times a_i + v \times a_j $$

将含 $i,j$ 的项分别放到左边，右边，得到：

$$a_i \times c_i - v\times a_i \ge v \times a_j - a_j \times c_j $$

发现两边的值都是确定的，我们分别算出。

然后就是这样一个问题了：

给出两个长度为 $n$ 的序列 $\{a_n\},\{b_n\}$，你需要求出有多少对 $(i,j)$，满足 $a_i \ge b_j$。

这是一个经典问题，比较简单的一个做法是将两个序列分别排序，然后使用双指针法 $O(n)$ 数出对数。

时间复杂度：$O(n\log v\log n)$。

参考代码

#include <cstdio>
#include <algorithm>
using namespace std; 
#define ll long long
#define eps 1e-3
int n;
ll k;
int a[100005],c[100005];//a 毫升,c 温度 
double p[100005],q[100005];

bool cmp(double a,double b){
	return a < b;
} 

int check(double v){
    ll tot = 0;
	for(int i = 1;i <= n;i++){
		double x = a[i] * 1.0 * c[i],y = v * a[i]; 
		p[i] = x - y;
		q[i] = y - x; 
		if(q[i] - p[i] < eps) tot--;
	}
	sort(p + 1, p + n + 1, cmp);
	sort(q + 1, q + n + 1, cmp);
	int j = 0;
	for(int i = 1;i <= n;i++){
		while((q[j + 1] - p[i]) < eps && j + 1 <= n) j++;
		tot += j;
	}
	return (tot / 2 < k);
}

int main(){
	scanf("%d%lld", &n, &k);
	for(int i = 1;i <= n;i++){
		scanf("%d%d",&a[i],&c[i]);
	}
	double l = 1,r = 1000000000,mid;
	while((r - l) > eps){
		mid = (l + r) / 2;
		if(check(mid)){
			r = mid;
		}
        else{
			l = mid;
		}
	}
	printf("%.3f\n", l);
	return 0;
}