NWERC2019-H

思路

根据题意可以发现答案肯定有一个在端点上，如果两个都不在端点上，那么可以通过平移得到相同的答案，所以最优的答案肯定有一个在端点上，考虑j在端点上。

$$\begin{aligned} \frac{y_{i+res}-y_j}{(i+res)-j}&=k\\ res&=\frac{(j_i-ik)-(y_j-jk)}{k_i-k}\\ k_i&=y_i-y_{i-1}\\ k_i-k&=(y_i-ik)-(y_{i-1}-(i-1)k)\\ 令tmp[i]&=y_i-ik\\ res&=\frac{tmp[i]-tmp[j]}{tmp[i]-tmp[i-1]} \end{aligned}$$

当然整数点也有可能在右边，所以在两段有可能有交点的地方都算出最大的偏移量。
res有答案肯定是tmp[i]-tmp[j]>0，然后我们处理好tmp的值，用来排序，并且还要保证$（j-i）>0$所以我们用L，R来表示当前的位置，从小到大遍历tmp数组，当L<R的时候就统计答案，L每次尽量向左走，然后R稳定向右走，答案肯定会最大。就是利用了单调性

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+10;
int h[N];
void solve(int k,int n){
    double ans = -1.0;
    vector<pair<int,int>>vec(n+1),tmp(n+1);
    for(int i=0;i<=n;i++){
        vec[i]=(make_pair(h[i]-i*k,i));
        tmp[i]=vec[i];
    }
    sort(vec.begin(),vec.end());
    int L = n,R;
    for(int i=0;i<vec.size();i++){
        R = vec[i].second;
        if(L<R){
            double res = 0;
            if(L>0)res=max(res,((tmp[R].first-tmp[L].first)/fabs(tmp[L].first-tmp[L-1].first)));
            if(R<n)res=max(res,((tmp[R].first-tmp[L].first)/fabs(tmp[R+1].first-tmp[R].first)));
            if(res>1.0)res=1.0;
            ans=max(ans,R-L+res);
        }
        L=min(L,R);
    }
    printf("%.12lf\n",ans);
}
int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    int maxh = -1;
    for(int i=0;i<=n;i++){
        scanf("%d",&h[i]);
        if(i!=0)
        maxh = max(maxh,h[i]-h[i-1]);
    }
    double q;
    while(k--){
        scanf("%lf",&q);
        if(q*10>maxh){
            printf("impossible\n");
            continue;
        }
        solve(q*10,n);
    }
}