【luoguP2989】[USACO10MAR]对速度的需要Need For Speed

题目描述

最大化平均值

二分一个(x)

(check):

(frac{F+sum_{i=1}^{n} X_{i} imes F_{i}}{M+sum_{i=1}^{n} X_{i} imes M_{i}}geq x)

(F+sum_{i=1}^{n} X_{i} imes F_{i} geq M imes x+sum_{i=1}^{n} X_{i} imes M_{i} imes x)

(F-M imes x+sum_{i=1}^{n} (X_{i} imes F_{i}-X_{i} imes M_{i} imes x)ge 0)

贪心的将(1)到(n)中大于(0)的((X_{i} imes F_{i}-X_{i} imes M_{i} imes 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
",i),flag=1;
	if(!flag) puts("NONE");
	return 0;
}