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

题目描述

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

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1

输出 #1

4.500

说明/提示

样例 1 说明

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

样例 2

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

数据规模与约定

本题采用捆绑测试。

子任务 1（9 pts）：有 (1le nle 10)
子任务 2（40 pts）：保证 (k=1)
子任务 3（50 pts）：无特殊限制。
子任务 4（1 pts）：Hack 数据。

对于 100% 的数据，有 (1le nle 10^5, 1le k le frac {n(n-1)} {2},1le a_i,c_i le 10^9)

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

前置知识

对于两杯体积、温度分别为((a_i,c_i),(a_j,c_j))的水，混合后温度为：

[T=frac {a_i c_i+ a_j c_j} {a_i+c_j} ]

思路

二分。

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

首先分析一下这道题目：

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

设这个第k大的温度值为v

[frac {a_ic_i+a_jc_j} {a_i+c_j}ge v ]

变形可以得到

[a_ic_i-v a_ige va_j-a_jc_j ]

问题就是求有多少i，j满足(a_ige b_j)

代码

#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
",ans);
	return 0;
}