最大化平均值 - 二分搜索

题意

有n个物品的重量和价值分别是 xi 和 vi . 从中选出k个物品使得单位重量的价值最大. 1<=k<=n<= 104 , 1<= wi , vi <= 106 .

题解1(二分搜索)

分析

check(x): 可以选择使得单位重量的价值不小于x.

二分搜索的难点在于check函数的编写和边界的移动.

代码

#include<set> #include<map> #include<ctime> //CLOCKS_PER_SEC;clock_t t=clock(); #include<cmath> #include<queue> #include<bitset> #include<cctype> #include<cstdio> #include<vector> #include<string> //getline(cin, line); #include<sstream> //stringstream ss(line);(ss is a stream like cin). #include<cstdlib> #include<cstring> #include<float.h> //X=FLT,DBL,LDBL;X_MANT_DIG,X_DIG,X_MIN_10_EXP,X_MIN_10_EXP,X_MIN,X_MAX,X_EPSILON #include<limits.h> //INT_MAX,LLONG_MAX #include<iostream> //ios_base::sync_with_stdio(false); #include<algorithm> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; const double PI = acos(-1.0); const int INF=0x3f3f3f3f; const int Max=1; int n, k, f[10009], w[10009]; bool check(double x){ double y[10009]; for(int i=0; i<n; i++) y[i]=f[i]-x*w[i]; sort(y, y+n); double sum=0; for(int i=0; i<k; i++) sum+=y[n-i-1]; return sum>=0; } int main(void){ //freopen("in", "r", stdin); freopen("out", "w", stdout); while(~scanf("%d%d", &n,&k)){ for(int i=0; i<n; i++) scanf("%d %d", w+i, f+i); double l=0, r=INF; for(int i=0; i<100; i++){ double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.2f\n", r); } return 0; }