E题的另一种理解

看了题解应该都知道是二分答案，二分答案关键在于怎么检验答案

• 如何检验答案 根据我们小学二年级学的，速度是相对的

  • 我们可以这么规定向左的速度为0，那么向右的速度为2

  此时我们可以一个一个计算向右的通过了多少个静止不动的

  • 例如，现在当前的向右的位置为，在当前时间下,到达+,因此只要在+内静止不动的都能被计算在内

  这下问题就转化成如何高效统计这个区间内静止的球：

  假如两个向右的球相邻，我们依次得到两个区间，区间的范围指的是静止不动的球的数组的下标

  那么必然 所以我们可以排序，然后利用双指针逐渐找到对于每一个向右的球的区间

CODE
(跟雨巨orz学的

#include<bits/stdc++.h>

using namespace std;
#define p first
#define v second
const int maxn=1e5+10;
typedef pair<int,int> pii;

int n,k;
vector<int>a,b;
bool check(double x){
    int cnt=0;
    int l=0,r=0;
    int len=b.size();
    for(auto i:a){
        while(l<len && b[l]<i) ++l;
        while(r<len && b[r]<=i+2*x) ++r;
        cnt+=r-l;
    }
    return cnt>=k;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        int p,v;
        cin>>p>>v;
        if(v==1)        a.push_back(p);
        else b.push_back(p);
    }    
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    double l=0,r=1e9+10;
    while((r-l)>1e-6){
        double mid=(l+r)/2;
        if(check(mid))          r=mid-1e-6;
        else l=mid+1e-6;
    }
    if(r==1e9+10) puts("No");
    else {
        puts("Yes");
        cout<<fixed<<setprecision(6)<<l<<"\n";
    }
}