本文主要是介绍poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
poj 2976：
题意：
在n场考试中，每场考试共有b题，答对的题目有a题。
允许去掉k场考试，求能达到的最高正确率是多少。
解析：
假设已知准确率为x，则每场考试对于准确率的贡献值为：
a - b * x，将贡献值大的排序排在前面舍弃掉后k个。
然后二分x就行了。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
const double ee = exp(1.0);
const int maxn = 1000 + 10;int n, k;
double x;
struct Test
{int a, b;bool operator < (const Test &t)const{return a - x * b > t.a - x * t.b;}
} test[maxn];bool ok(double mi)
{x = mi;sort(test, test + n);double sumA = 0, sumB = 0;for (int i = 0; i < n - k; i++){sumA += test[i].a;sumB += test[i].b;}return mi < (sumA / sumB);
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALwhile (~scanf("%d%d", &n, &k)){if (!n && !k)break;for (int i = 0; i < n; i++){scanf("%d", &test[i].a);}for (int i = 0; i < n; i++){scanf("%d", &test[i].b);}double lo = 0, hi = 1.0;for (int i = 0; i <= 100; i++){double mi = (lo + hi) / 2;if (ok(mi))lo = mi;elsehi = mi;}printf("%.0lf\n", lo * 100);}return 0;
}
poj 3111：
也是贡献度的问题，不一样的就是循环的次数过多会超时和输出答案。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
const double ee = exp(1.0);
const int maxn = 100000 + 10;int n, k;
double x;
struct Jewel
{int v, w;int id;bool operator < (const Jewel &t)const{return v - x * w > t.v - x * t.w;}
} jewel[maxn];
int ans[maxn];bool ok(double mi)
{x = mi;sort(jewel, jewel + n);double sumV = 0, sumW = 0;for (int i = 0; i < k; i++){sumV += jewel[i].v;sumW += jewel[i].w;}return mi < (sumV / sumW);
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALwhile (~scanf("%d%d", &n, &k)){double maxx = 0;for (int i = 0; i < n; i++){scanf("%d", &jewel[i].v);scanf("%d", &jewel[i].w);jewel[i].id = i;maxx = max(maxx, (double)jewel[i].v / jewel[i].w);}double lo = 0, hi = maxx;for (int i = 0; i <= 50; i++){double mi = (lo + hi) / 2;if (ok(mi))lo = mi;elsehi = mi;}for (int i = 0; i < k; i++){ans[i] = jewel[i].id + 1;}sort(ans, ans + k);for (int i = 0; i < k; i++){printf("%d%c", ans[i], i == k - 1 ? '\n' : ' ');}}return 0;
}
这篇关于poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
