【题解】AT_cf_2015_morning_hard_h ありんこ

最小值最大确实是二分。一般是想二分 + 贪心。但是这道题套的是 DP。不能直接 DP 的原因是，它是一个 2D1D 的转移，然而代价函数长这样：

t(i,j)=\frac{x_i-x_j}{v_j-v_i}

这个东笔者已经替你们思考了四个半小时了，它没有单调性、限制后的 1D 问题不是凸包、不满足四边形不等式。妥妥的

\mathcal O(n^3)

优化不了。

考虑回二分，二分能让我们得到什么？多出来一个最低代价

mid

的限制。于是要保证选出的任意

i,j

满足

\frac{x_i-x_j}{v_j-v_i}\ge mid

，于是就可以分离变量了，强令

x_i<x_j

，得到

x_j-x_i\ge (v_i-v_j)mid

，再化一下变量就分离啦：

x_j+v_j\cdot mid\ge x_i+v_i\cdot mid

，但要记住我们钦定了

x_i<x_j

。

在 DP 之前，还要证一个东西。
注意到如果某一小球

i

能对碰撞答案产生贡献，必然由和其相邻的小球碰撞产生。证明：

对

(i,i-1)

和

(i,i+1)

的证明本质相同，只证

(i,i+1)

的情况。

若 $v_i>v_{i+1}$ ，这两个能相创，如果有一个小球 $j$ 使得它和 $i$ 相创的时间早于 $i$ 和 $i+1$ 相创，则其必定和 $i+1$ 更早相创，于是不贡献答案；
若 $v_i\le v_{i+1}$ 则几乎和上面同理，甚至还少一个 $i$ 和 $i+1$ 相创的竞争条件。

于是令

b_i=x_i+v_i\cdot mid

，约束化为了一个

b

上的 LIS 问题，二分栈就做完了。时复

\mathcal O(n\log n\log V)

，其中

V

是值域上限。

AC 代码

CPP

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#define ll long long
#define I_love_Hina return //Amano Hina
#define forever 0
using namespace std;
template<class T>
inline void read(T &x)
{
	char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10-48+c,c=getchar();
}
struct bal{int x,v;}b[100005];
int n,k;
const double eps=1e-8;
double a[100005],st[100005];
int top;
bool chk(double m)
{
	for(int i=1;i<=n;i++) a[i]=m*b[i].v+b[i].x;
	top=0;
	for(int i=1;i<=n;i++)
	{
		if(!top||st[top]<a[i])
		{
			st[++top]=a[i];
			if(top>=n-k) return true;
		}
		else st[lower_bound(st+1,st+top+1,a[i])-st]=a[i];
	}
	return false;
}
int main()
{
	read(n);read(k);
	for(int i=1;i<=n;i++)
	{
		read(b[i].x);read(b[i].v);
		char c=getchar();
		while(!isalpha(c)) c=getchar();
		if(c=='L') b[i].v=-b[i].v;
	}
	sort(b+1,b+n+1,[](bal u,bal v)->bool{return u.x<v.x;});
	double l=0,r=1e10,mid;
	while(r-l>eps)
	{
		mid=(l+r)/2;
		if(chk(mid)) l=mid;
		else r=mid;
	}
	if(l>1e10-1000) printf("Infinity");
	else printf("%07lf",l);
	I_love_Hina forever;
}

【题解】AT_cf_2015_morning_hard_h ありんこ

文章操作

AC 代码

相关推荐

评论

【题解】AT_cf_2015_morning_hard_h ありんこ