首页 > 代码库 > POJ 2976 二分求平均值最大
POJ 2976 二分求平均值最大
题意： n个物品有重量w价值v，取出k个使得单位重量价值最大。
思路：
二分，单位重量价值a = sigama(v) / sigama(w)，令左<=右，转移方程有 sigama(v - a*w) >= 0。----1
对于二分查找单位重量价值a，排序求出最大k个物品使得sigama(v - a*w)最大。
此时：
若条件1满足，则显然存在更好的方案，因为至少还有该方案。
若条件1不满足，则不存在更好的方案：
反证：现有 sigama(v1 - a1*w1) < 0 即 a1 > sigama(v1)/sigama(w1) 记为方案1，若存在方案2使得sigama(v2)/sigama(w2) = a2 > a1，则有sigama(v2)/sigama(w2) = a2 > a1 > sigama(v1)/sigama(w1) 与计算sigama(v - a*w) >= 0时取最大方案矛盾，故成立
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define INF 0x3f3f3f3fusing namespace std;double a[1005], b[1005], w[1005];int n, k;int main(){ while(scanf("%d%d", &n, &k) != EOF && n) { k = n-k; for(int i = 0; i < n; i ++) scanf("%lf", &a[i]); for(int i = 0; i < n; i ++) scanf("%lf", &b[i]); double l = 0, r = 1; while(r-l > 1e-4) { double mid = (l+r)/2; for(int i = 0; i < n; i ++) w[i] = a[i]-mid*b[i]; sort(w, w+n); double max = 0; for(int i = n-1; i >= n-k; i --) max += w[i]; if(max >= 0) l = mid; else r = mid; } printf("%.f\n", l*100); } return 0;}
其实这题若单纯想很容易想到二分法，不过细想反而可能想歪掉。
对于最优方案v、w、a，有 a>a‘，有sigama(v-a *w) == 0 且 永远保证 sigama(v - a‘ *w) >= 0，不过并不能保证sigama(v - a‘ *w)最大。
也就是说 sigama(v - a‘ *w) >= 0条件和最优方案是等价的。
POJ 2976 二分求平均值最大
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。