【解题报告】 洛谷P6733 间歇泉

题目描述

有一个间歇泉，冒出了 n 杯水，由于一些原因，每杯水的温度、体积不同。第 i 杯水的温度为 ci体积为 ai

现在混合任意两杯水，每混合两杯水都会得到一个新的温度值，求可能得到的第 kkk 高的温度值（不计热量损失）。

你的答案建议至少保留小数点后 3 位（与标准答案之差在 10−210^{-2} 以内即视为通过）。

输入格式

第一行一个数 n,k，意义如题述。

接下来 n行，每行两个数 ai,c

输出格式

一行一个实数，表示混合后的水的第 kkk 高温度。

输入输出样例

输入 #1

1
2
3
4
5
6
5 1
1 5
4 2
5 3
2 3
1 4

输出 #1

1
4.500

说明/提示

样例 1 说明

第 1 和第 5杯水混合，得到 4.5的温度值。可以发现，这是可能得到的最高水温。

样例 2

见题目附件中 pour2.in 与 pour2.ans。

数据规模与约定

本题采用捆绑测试。

  • 子任务 1（9 pts）：有 1≤n≤101\le n\le 10
  • 子任务 2（40 pts）：保证 k=1k=1
  • 子任务 3（50 pts）：无特殊限制。
  • 子任务 4（1 pts）：Hack 数据。

对于 100% 的数据，有 1≤n≤105,1≤k≤n(n−1)2,1≤ai,ci≤1091\le n\le 10^5, 1\le k \le \frac {n(n-1)} {2},1\le a_i,c_i \le 10^9

子任务 2/3/4 时限 2s，子任务 1 时限 1s。

前置知识

对于两杯体积、温度分别为(ai,ci),(aj,cj)(a_i,c_i),(a_j,c_j)的水，混合后温度为：
T=aici+ajcjai+cj T=\frac {a_i c_i+ a_j c_j} {a_i+c_j}

思路

二分。

这道题符合我们的求第k大的数的形式，因此我们可以进行二分答案来做题目。

首先分析一下这道题目：

可以混合任意两杯水来得到温度值，找第k大的温度值

设这个第k大的温度值为v
aici+ajcjai+cj≥v \frac {a_ic_i+a_jc_j} {a_i+c_j}\ge v

变形可以得到
aici−vai≥vaj−ajcj a_ic_i-v a_i\ge va_j-a_jc_j
问题就是求有多少i，j满足ai≥bja_i\ge b_j

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const double eps=0.001;
int n,k;
int a[100005],c[100005];
double p[100005],q[100005];
long double ans;
bool cmp(double a,double b)
{
	return a<b;
}
bool check(double v)
{
	long long 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+1+n,cmp);
	sort(q+1,q+1+n,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()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	cin>>a[i]>>c[i];
	long double l=1,r=1e9,mid;
	while(r-l>eps)
	{
		mid=(l+r)/2;
		if(check(mid)) r=mid,ans=mid;
		else l=mid;
	}
	printf("%.3Lf\n",ans);
	return 0;
}