挑战程序竞赛系列（17）：3.1最大化平均值
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434623
挑战程序竞赛系列（17）：3.1最大化平均值
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
POJ 2976: Dropping tests
01分数规划，具体可以参考博文http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html，写的非常详细且通俗易懂。
我的认识：中学里学过二分法求函数零点，其实该代码模拟的就是这种求解过程，所以只要写出目标函数，零点不难求。
接着就得到了求和式：
∑i=1n(ai−l⋅bi)≥0
\sum_{i = 1}^n (a_i - l \cdot b_i) \ge 0
要删除k个物品，当然选择贡献最小的，所以按照ai−l⋅bia_i - l \cdot b_i排序，选择n-k个物品，排除其余贡献较小的k个物品。
代码如下：
static class Pair implements Comparable<Pair>{
int a;
int b;
@Override
public int compareTo(Pair o) {
double ocmp = o.a - L * o.b;
double tcmp = this.a - L * this.b;
return ocmp == tcmp ? 0 : (ocmp > tcmp) ? 1 : -1;
}
}
static Pair[] p;
static double L;
static int k;
static int n;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
while (true){
n = in.nextInt();
k = in.nextInt();
if (n == 0 && k == 0) break;
p = new Pair[n];
for (int i = 0; i < n; ++i){
p[i] = new Pair();
p[i].a = in.nextInt();
}
for (int i = 0; i < n; ++i){
p[i].b = in.nextInt();
}
double lf = 0;
double rt = 1;
while (Math.abs(rt -lf) > 1e-4){
double mid = (lf + rt) / 2;
if (!valid(mid)) rt = mid;
else lf = mid;
}
System.out.printf("%.0f\n",lf * 100);
}
}
public static boolean valid(double mid){
L = mid;
Arrays.sort(p);
double sum = 0;
for (int i = 0; i < n - k; ++i){
sum += (p[i].a - L * p[i].b);
}
return sum > 0;
}POJ 3111: K Best
和上一题一个思路，但此题精度要求要高很多，按照上一题的while循环，WA了，测了下，大概循环14次左右，而此题循环50次，可以达到0.000000001的精度。注意记录下下标。
代码如下：
static class Pair implements Comparable<Pair>{
int a;
int b;
int id;
@Override
public int compareTo(Pair o) {
double that = o.a - L * o.b;
double thiz = this.a - L * this.b;
return that == thiz ? 0 : (that > thiz) ? 1 : -1;
}
}
static double L;
static Pair[] p;
static int N;
static int K;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
N = in.nextInt();
K = in.nextInt();
p = new Pair[N];
ans = new int[K];
for (int i = 0; i < N; ++i) p[i] = new Pair();
double max = 0;
for (int i = 0; i < N; ++i){
p[i].a = in.nextInt();
p[i].b = in.nextInt();
p[i].id = i + 1;
max = Math.max(max, p[i].a / (p[i].b * 1.0 ));
}
double lf = 0.0;
double rt = max;
for (int i = 0; i < 50; ++i){
double mid = (lf + rt) / 2;
if (!valid(mid)) rt = mid;
else lf = mid;
}
for (int i = 0; i < K; ++i) ans[i] = p[i].id;
StringBuilder sb = new StringBuilder();
Arrays.sort(ans);
for (int i : ans){
sb.append(i + " ");
}
System.out.println(sb.toString().trim());
}
static int[] ans;
public static boolean valid(double mid){
L = mid;
Arrays.sort(p);
double sum = 0.0;
for (int i = 0; i < K; ++i){
sum += (p[i].a - L * p[i].b);
}
return sum > 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017年06月23日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
