题目
题目链接：https://gmoj.net/senior/#main/show/4017
Konrad， Delfador 和 Kalenz 一行人又喜闻乐见地被追杀了。
他们面临的是一条有 N 个地点的路， 他们从 0 号地点出发， 要逃到 N 号地点去。每个地点的战斗都有一定的金币收入 Ai，也有一定的部队损失 Bi。
为了更好地逃生， Delfador 还弄到了一块传送宝石，这样一行人就能向后传送不超过 L 的距离。从一个地点传送到另一个地点时，Konrad 会选择路径上除起点外的地形指数 Ci 最大的地点进行战斗，地形指数相同时选择最靠后的。
作为优秀的领导者， Konrad 希望总金币收入与总部队损失的比值最大。
思路
如果没有长度\(L\)的限制，以及找\(c\)最大的地方打架的限制，那么这道题就是一个裸的\(01\)分数规划的问题。
有了这些限制后依然一样，先二分\(mid\)表示\(\frac{\sum A_i}{\sum B_i}\geq mid\)，然后判断能否选出一些\(i\)满足上式。
那么我们要让\(\sum (A_i-mid\times B_i)\)大于零。
设\(f[i]\)表示跳到点\(i\)时，\(\sum (A_j-mid\times B_j)\)的最大值，其中\(j\)是选择的落脚点。
那么先预处理出每一个点的影响区间\([l_i,r_i]\)，意思是在\([l_i,r_i]\)的点如果跳到点\(i\)后面，将会在\(i\)处打架。
这个可以用平衡树、线段树、\(bit\)、单调队列+二分等东西在\(O(n\log n)\)的时间复杂度内求出来，具体方法留作思考（雾
那么显然有转移
\[f[i]=max(f[j]+A_k-B_k\times mid)$$，$k$应该为$(j,i]$中$c$最大且尽量靠后的那一个。
如果$f[n]\geq 0$，那么$mid$就过小，否则过大。
# 代码
特别丑+调到自闭。
```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=300010,Inf=1e9;
int n,m,a[N],b[N],c[N],d[N],L[N],R[N];
double f[N];
struct Segnode
{
int l,r,mn;
};
struct SegTree
{
Segnode tree[N*4];
void pushup(int x)
{
tree[x].mn=max(tree[x*2].mn,tree[x*2+1].mn);
}
void build(int x,int l,int r,int val)
{
tree[x].l=l; tree[x].r=r; tree[x].mn=val;
if (l==r) return;
int mid=(l+r)>>1;
build(x*2,l,mid,val);
build(x*2+1,mid+1,r,val);
}
int ask(int x,int l,int r)
{
if (tree[x].l==l && tree[x].r==r)
return tree[x].mn;
int mid=(tree[x].l+tree[x].r)>>1;
if (r<=mid) return ask(x*2,l,r);
if (l>mid) return ask(x*2+1,l,r);
return max(ask(x*2,l,mid),ask(x*2+1,mid+1,r));
}
void update(int x,int k,int val)
{
if (tree[x].l==k && tree[x].r==k)
{
tree[x].mn=val;
return;
}
int mid=(tree[x].l+tree[x].r)>>1;
if (k<=mid) update(x*2,k,val);
else update(x*2+1,k,val);
pushup(x);
}
}seg;
struct Segnode2
{
int l,r;
double maxn,f,k,lazy;
};
struct SegTree2
{
Segnode2 tree[N*4];
void pushup(int x)
{
tree[x].maxn=max(tree[x*2].maxn,tree[x*2+1].maxn);
tree[x].f=max(tree[x*2].f,tree[x*2+1].f);
}
void pushdown(int x)
{
if (tree[x].lazy)
{
tree[x*2].maxn=tree[x*2].f+tree[x].lazy;
tree[x*2+1].maxn=tree[x*2+1].f+tree[x].lazy;
tree[x*2].k=tree[x*2].lazy=tree[x].lazy;
tree[x*2+1].k=tree[x*2+1].lazy=tree[x].lazy;
tree[x].lazy=0;
}
}
void build(int x,int l,int r)
{
tree[x].l=l; tree[x].r=r; tree[x].lazy=0;
tree[x].maxn=tree[x].f=tree[x].k=-100000000000.0;
if (l==r) return;
int mid=(l+r)>>1;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
}
double ask(int x,int l,int r)
{
if (l>r) return -1000000000000.0;
if (tree[x].l==l && tree[x].r==r)
return tree[x].maxn;
pushdown(x);
int mid=(tree[x].l+tree[x].r)>>1;
if (r<=mid) return ask(x*2,l,r);
if (l>mid) return ask(x*2+1,l,r);
return max(ask(x*2,l,mid),ask(x*2+1,mid+1,r));
}
void updatef(int x,int k,double val)
{
if (tree[x].l==k && tree[x].r==k)
{
tree[x].f=val;
return;
}
int mid=(tree[x].l+tree[x].r)>>1;
if (k<=mid) updatef(x*2,k,val);
else updatef(x*2+1,k,val);
pushup(x);
}
void updatek(int x,int l,int r,double val)
{
if (tree[x].l==l && tree[x].r==r)
{
tree[x].k=tree[x].lazy=val;
tree[x].maxn=tree[x].f+tree[x].k;
return;
}
pushdown(x);
int mid=(tree[x].l+tree[x].r)>>1;
if (r<=mid) updatek(x*2,l,r,val);
else if (l>mid) updatek(x*2+1,l,r,val);
else updatek(x*2,l,mid,val),updatek(x*2+1,mid+1,r,val);
pushup(x);
}
}seg2;
bool check(double mid)
{
seg2.build(1,0,n);
seg2.updatef(1,0,0.0);
for (int i=1;i<=n;i++)
{
seg2.updatek(1,L[i],i-1,1.0*a[i]-1.0*b[i]*mid);
f[i]=seg2.ask(1,max(i-m,0),i-1);
seg2.updatef(1,i,f[i]);
}
return f[n]>=0.0;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
d[i]=c[i];
}
sort(d+1,d+1+n);
int cnt=unique(d+1,d+1+n)-d-1;
for (int i=1;i<=n;i++)
c[i]=lower_bound(d+1,d+1+cnt,c[i])-d;
seg.build(1,1,cnt+1,0);
for (int i=1;i<=n;i++)
{
L[i]=max(max(0,i-m),seg.ask(1,c[i]+1,cnt+1));
seg.update(1,c[i],i);
}
double l=0.00001,r=1000000.0,mid;
while (r-l>0.0000000003)
{
mid=(l+r)/2.0;
if (check(mid)) l=mid;
else r=mid;
}
cnt=0;
for (;l>=10.0;cnt++) l/=10.0;
for (;l<=1.0;cnt--) l*=10.0;
printf("%0.9lfe",l);
if (cnt<0) printf("-");
else printf("+");
cnt=abs(cnt);
if (cnt<10) printf("00%d",cnt);
else if (cnt<100) printf("0%d",cnt);
else printf("%d",cnt);
return 0;
}
```\]