P2877 [USACO07JAN]牛校Cow School
决策单调性分治，可以解决（不限于）一些你知道要用斜率优化却不会写的问题
怎么证明？可以暴力打表
我们用$ask(l,r,dl,dr)$表示处理区间$[l,r]$时，这段区间的决策点已固定在$[dl,dr]$中
设$mid=(l+r)/2$，暴力处理$mid$的最优决策点$dm$
再向下分治$ask(l,mid-1,dl,dm)$，$ask(mid+1,r,dm,dr)$
对于本题，先按$t[i]/p[i]$从大到小排序，排序后的默认方案（删掉后D个）即为
取区间$[1,n-D]$，舍去区间$[n-D+1,D]$
怎么判断默认方案是否最优呢
根据01分数规划的基本套路（大雾）
设$r=st[i]/sp[i]$（$st[i],sp[i]$为排序后$t,p$的前缀和）
在$[1,n-D]$中找到$A=min{t[i]-r*p[i]}$
在$[n-D+1,n]$中找到$B=max{t[i]-r*p[i]}$
如果$A<B$，那么交换A，B可以使答案更优，即默认方案不是最佳方案
于是就可以分治处理辣
复杂度$O(nlogn)$
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 50005
struct data{ll t,p;}a[N];
int n,ans; ll f[N],g[N],st[N],sp[N];
inline bool cmp(data A,data B){return A.t*B.p>A.p*B.t;}
void getf(int l,int r,int dl,int dr){
int mid=(l+r)>>,dm;
f[mid]=1e16;
for(int i=dl;i<=min(mid,dr);++i){
ll tt=sp[mid]*a[i].t-st[mid]*a[i].p;
if(tt<f[mid]) f[mid]=tt,dm=i;
}
if(l<mid) getf(l,mid-,dl,dm);
if(r>mid) getf(mid+,r,dm,dr);
}
void getg(int l,int r,int dl,int dr){
int mid=(l+r)>>,dm;
g[mid]=-1e16;
for(int i=dr;i>=max(mid+,dl);--i){
ll tt=sp[mid]*a[i].t-st[mid]*a[i].p;
if(tt>g[mid]) g[mid]=tt,dm=i;
}
if(l<mid) getg(l,mid-,dl,dm);
if(r>mid) getg(mid+,r,dm,dr);
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i) scanf("%lld%lld",&a[i].t,&a[i].p);
sort(a+,a+n+,cmp);
for(int i=;i<=n;++i) st[i]=a[i].t+st[i-],sp[i]=a[i].p+sp[i-];
getf(,n-,,n); getg(,n-,,n);
for(int i=;i<n;++i) if(f[i]<g[i]) ++ans;
printf("%d\n",ans);
for(int i=n-;i;--i) if(f[i]<g[i]) printf("%d\n",n-i);
return ;
}