题意：
一个人参加了 (n) 场考试，第 (i) 场满分为 (p_i)，其得分为 (t_i)。现在要删去其中 (d) 次考试的成绩，用剩下的总得分除以剩下的满分之和，作为其最终成绩。问对于哪些 (d) 而言，删除得分比(即 (frac{t_i}{p_i}) )最小的 (d) 场得到的最终成绩不是最优的
范围&性质：(1le nle 5 imes 10^4,1le p_i,t_ile 4 imes 10^4)
分析：
首先这个式子长得很分数规划，但是按照正常分数规划的做法，复杂度是(O(n^2log n))的，直接去世
我们发现其实并不需要求出分数规划的答案，我们只需要知道选的数是不是最小的 (d) 个，那就按照正常分数规划的套路，求出所有的 (t-rate imes p) ，如果未选的最大值大于已选的最小值，那么该方案一定不是最优，所以问题就转化成了求前缀序列的最小值和后缀序列的最大值
由于 (t-rate imes p) 这种形式很斜率优化，且 (rate) 是单调的，能成为决策点的 (p_i) 也是单调的
- 证明：
对于 (t_i-rate imes p_i<t_j-rate imes p_j) 且 (i<j)
由于 (frac{t_i}{p_i}le frac{t_j}{p_j}) 所以当 (p_j>p_i) 时存在 (frac{t_j-t_i}{p_j-p_i}>rate) 即 (j) 可以成为决策点
然后我们就可以按照正常的斜率优化的做法解题，对于求已选的最小值可以用单调队列维护一个递增的序列，对于未选的最大值可以用单调栈维护递减的值
代码：
#include<bits/stdc++.h>
using namespace std;
namespace zzc
{
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 5e4+5;
int n,h,t,top,ans;
int q[maxn],sumt[maxn],sump[maxn],pos[maxn];
double hig[maxn],low[maxn];
struct node
{
int p,t;
bool operator<(const node &b)const
{
return p*b.t<b.p*t;
}
}a[maxn];
int up(int x,int y)
{
return (a[x].p-a[y].p);
}
int down(int x,int y)
{
return (a[x].t-a[y].t);
}
void work()
{
n=read();
for(int i=1;i<=n;i++) a[i].t=read(),a[i].p=read();
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) sumt[i]=sumt[i-1]+a[i].t,sump[i]=sump[i-1]+a[i].p;
h=1;t=0;
for(int i=1;i<=n;i++)
{
while(h<=t&&a[i].p>=a[q[t]].p) t--;
while(h<t&&(long long)up(q[t-1],q[t])*down(q[t],i)>(long long)up(q[t],i)*down(q[t-1],q[t])) t--;
q[++t]=i;
while(h<t&&(long long)down(q[h],q[h+1])*sump[i]>(long long)up(q[h],q[h+1])*sumt[i]) h++;
low[i]=a[q[h]].t-(double)sumt[i]/sump[i]*a[q[h]].p;
}
top=0;
for(int i=n;i>=1;i--)
{
while(top&&a[i].p<=a[q[top]].p) top--;
while(top>1&&(long long)down(i,q[top])*up(q[top],q[top-1])>(long long)up(i,q[top])*down(q[top],q[top-1])) top--;
q[++top]=i;
while(top>1&&(long long)down(q[top],q[top-1])*sump[i-1]<=(long long)up(q[top],q[top-1])*sumt[i-1]) top--;
hig[i]=a[q[top]].t-(double)sumt[i-1]/sump[i-1]*a[q[top]].p;
}
for(int i=1;i<n;i++) if(hig[i+1]>low[i]) pos[++ans]=n-i;
printf("%d
",ans);
for(int i=ans;i>=1;i--) printf("%d
",pos[i]);
}
}
int main()
{
zzc::work();
return 0;
}