标签：P6733 frac Wdsr int res double mul 间歇泉 displaystyle

二分可以将优化问题转为判定问题，也可以将\(k\)大问题转为计数问题

分析

由于已知条件，\(\displaystyle T=\frac{a_ic_i+a_jc_j}{a_i+a_j}\)，转为计数问题则是固定T，统计有多少对无序对\((i,j)\)满足\(\displaystyle T\le\frac{a_ic_i+a_jc_j}{a_i+a_j}\)
我们可以固定\(i\)，通过某种方式直接统计相应的\(j\)
分两种情况：

• 两个初始温度均高于\(T\)，则合并后必定高于\(T\)，统计所有这样的个数\(r\)，这部分个数为\(\displaystyle \frac{n(n-1)}{2}\)
• 一个初温低于\(T\)，一个初温高于\(T\)，枚举温度低的，可以直接统计温度高的个数

第二种情况的枚举较为麻烦，我们设温度低的为\(i\)，温度高的为\(j\)，则\(i,j\)需要满足：

\[a_i(T-c_i)\le a_j(c_j-T) \]

我们将所有元素按照\(a_i(c_j-T)\)从小到大排序，查找表中大于等于\(a_i(T-c_i)\)的个数（lower_bound）即可

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const double eps=1e-5;
const int N=1e5+5;

int n;ll k;

double a[N],c[N];

double mul[N];

bool judge(double T) {
	ll res=0;
	for(int i=1;i<=n;i++) {
		mul[i]=a[i]*(c[i]-T);
		if(mul[i]>=0)
		  res++;
	}
	res=(res)*(res-1)/2;	//第一部分
	sort(mul+1,mul+n+1);
	for(int i=1;i<=n;i++) {	//第二部分
		if(c[i]>=T) continue;
		res+=n+1-(lower_bound(mul+1,mul+n+1,a[i]*(T-c[i]))-mul);
	}
	
	return res>=k;
}

int main() {
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++)
	  scanf("%lf%lf",&a[i],&c[i]);
	double l=1,r=1e9;
	while(r-l>eps) {	//实数二分
		double mid=(l+r)/2;
		if(judge(mid))
		  l=mid;
		else
		  r=mid;
	}
	printf("%.3lf",l);
	return 0;
}

后记

为什么\(\displaystyle T=\frac{a_ic_i+a_jc_j}{a_i+a_j}\)？（如果\(c_i<c_j\)）
我们重新标一下字母，\(V,t\)指体积和温度
则\(\displaystyle T=\frac{V_it_i+V_jt_j}{V_i+V_j}\)
根据热平衡方程：

\[Q_{\text{吸}}=Q_{\text{放}} \]

\[c_{\text{水}}m_i\Delta t_i=c_{\text{水}}m_j\Delta t_j \]

\[m_i(T-t_i)=m_j(t_j-T) \]

\[T=\frac{m_it_i+m_jt_j}{m_i+m_j} \]

又

\[m=\rho_{\text{水}}V \]

所以

\[T=\frac{V_it_i+V_jt_j}{V_i+V_j} \]

标签：P6733,frac,Wdsr,int,res,double,mul,间歇泉,displaystyle
From： https://www.cnblogs.com/wyc06/p/16590824.html