【Codeforces 639E】Bear and Paradox
贪心，二分答案。
题目大意：
有 $n$ 道题，每道题有一个初始得分 $p_i$ 和做这道题需要花费的时间 $t_i$。令 $T=\sum\limits_{i=1}^n t_i$。
还有一个实数 $c\in[0,1]$。
你需要安排做题的顺序，并按顺序做题。第 $i$ 道题的最终得分为 $p_i\times(1-\frac{c\cdot x}{T})$，$x$ 表示从一开始到你做完这道题花费的总时间。
要求保证，不存在一种最优策略，对于满足 $p_i\lt p_j$ 的 $i,j$，$i$ 题最终得分严格大于 $j$ 题最终得分。最优策略指总分最大的策略。
求能够满足条件的 $c$ 的最大值。
题解：
考虑一种做题的顺序，交换相邻两道题对答案产生的贡献的差值。假设交换的题目为 $p_1,p_2$，时间为 $t_1,t_2$，之前的题的时间总和为 $t_0$。
所以最优策略满足 $\frac{p_i}{t_i}$ 单调不上升。否则一定可以通过交换相邻两个使答案变大。
对于 $\frac{p_i}{t_i}$ 相同的题目，可以任意交换顺序，不会影响答案。我们可以对于每道题，求出它最早完成的时间和最晚完成的时间（分别放在 $\frac{p_i}{t_i}$ 相同的题的最前面和最后面）。
由于 $c$ 满足单调性，所以考虑二分答案。
我们要求判断的是，对于 $p_i \lt p_j$ 是否能让 $j$ 题比 $i$ 题得分低。
我们按照 $p_i$ 从小到大排序。
对每个题 $i$，我们要尽可能让它的得分小（使用最晚完成时间计算），并和前面的题比较。而对于前面的题，我们要尽可能让它的得分大（使用最早完成时间计算）。如果前面题的最大得分超过当前题的最小得分，则这个 $c$ 不可行。
我们不需要每次都暴力对每个判断，只需要记录前缀最大得分即可。
时间复杂度 $O(n\log n)$。
Code：
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
struct prob{
int t,p;LL Ft,Lt;
inline bool operator<(const prob&rhs)const{return(LL)p*rhs.t>(LL)rhs.p*t;}
}a[150005];
inline bool cmp(const prob&a,const prob&b){return a.p<b.p;}
int n;
LL T;
bool check(double c){
double mx=0;
int lst=1;
for(int i=2;i<=n+1;++i)
if(a[i].p!=a[lst].p){
for(int j=lst;j<i;++j)
if(mx>a[j].p*(1-c*a[j].Lt/T))return 0;
for(int j=lst;j<i;++j)
mx=max(mx,a[j].p*(1-c*a[j].Ft/T));
lst=i;
}
return 1;
}
void init(){
sort(a+1,a+n+1);
LL ft=0,lt=0;
for(int i=1;i<=n;++i)
if(i==1||a[i-1]<a[i]){
ft=lt;
lt+=a[i].t;
for(int j=i+1;j<=n&&!(a[j-1]<a[j]);++j)lt+=a[j].t;
a[i].Ft=ft+a[i].t,a[i].Lt=lt;
for(int j=i+1;j<=n&&!(a[j-1]<a[j]);++j)
a[j].Ft=ft+a[j].t,a[j].Lt=lt;
}
sort(a+1,a+n+1,cmp);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i].p);
for(int i=1;i<=n;++i)scanf("%d",&a[i].t),T+=a[i].t;
init();
double l=0,r=1;
for(int i=1;i<=40;++i){
const double mid=(l+r)/2;
if(check(mid))l=mid;else r=mid;
}
printf("%.9g\n",l);
return 0;
}