最大化平均值
二分一个\(x\)
\(check\):
\(\frac{F+\sum_{i=1}^{n} X_{i} \times F_{i}}{M+\sum_{i=1}^{n} X_{i} \times M_{i}}\geq x\)
\(F+\sum_{i=1}^{n} X_{i} \times F_{i} \geq M \times x+\sum_{i=1}^{n} X_{i} \times M_{i} \times x\)
\(F-M \times x+\sum_{i=1}^{n} (X_{i} \times F_{i}-X_{i} \times M_{i} \times x)\ge 0\)
贪心的将\(1\)到\(n\)中大于\(0\)的\((X_{i} \times F_{i}-X_{i} \times M_{i} \times x)\)加起来,判断一下就可以了
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=10010;
int n,M,F,f[MAXN],m[MAXN];
inline bool check(double x){
double sum=F-M*x;
for(int i=1;i<=n;++i)
sum+=max(0.0,f[i]-m[i]*x);
return sum>=0;
}
int main()
{
scanf("%d%d%d",&F,&M,&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&f[i],&m[i]);
double l=0,r=1e18;
while(r-l>0.001){
double mid=(l+r)/2.0;
if(check(mid)) l=mid;
else r=mid;
}
bool flag=0;
for(int i=1;i<=n;++i)
if(f[i]-m[i]*l>0) printf("%d\n",i),flag=1;
if(!flag) puts("NONE");
return 0;
}