【题解】AT_cf_2015_morning_hard_h ありんこ

hez_EX · 2024-11-25 10:36:42 · 题解

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

这个东笔者已经替你们思考了四个半小时了，它没有单调性、限制后的 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 代码

#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;
}