本文共 3399 字，大约阅读时间需要 11 分钟。
题目链接： http://poj.org/problem?id=3111
题目描述： 在N个物品中让你选出K个， 使得平均价值最大
解题思路： 这是我错的代码......一会儿回来改啊......一会儿回来可能会很沮丧
---------*----------*----------*----------
我把错的代码删了， 不行看不下去， 确实很沮丧.......我对自己很失望
这题有毒........二分会超时， 我一直以为for i 1 to 100 这种方式会比 high - low > le-8 这种要优越呢， 其实并没有......因为前一种可能会超时的啊.........要是这道题卡常那不就GG了， 事实证明， 这道题是真的卡常， 讨论区里有好多都说这题有毒........我最后试试i == 50 时候不T， 而其他的时候都超时.......这不就是很伤的吗......
下面说说这道题的做法， 我们最大化平均值的时候首先想到的就是二分， 我们设G(x) 为单位的重量不小于X， 我们的目标就是要找到满足条件的最大的X， 也就是说我们的OK函数就要判断是否能够找到一个大小为K的集合S， 使得单位重量的价值大于等于X， 我们将当时变形转化为vi - x*wi >= 0 对于 所有的i 属于集合S， 这时我们对于一个整体值vi-x*wi的值的 排序， 贪心的选取前K个， 这样OK函数就写好了， 剩下问题就简单了
代码：
//#include //#include //#include //#include //#include //#include //#include //#include //#include //#include //#include //#include //#define lson l, m, rt<<1//#define rson m+1, r, rt<<1|1//#define mem0(a) memset(a,0,sizeof(a))//#define sca(x) scanf("%d",&x)//#define de printf("=======\n")//typedef long long ll;//using namespace std;////const double INF = 20000000.0;//const int maxn = 1e5+10;//int n, k;//struct node {// double v;// int index;// bool operator < (const node & rhs) const {// return v > rhs.v;// }//}y[maxn];//double v[maxn], w[maxn];////bool ok( double x ) {// for( int i = 0; i < n; i++ ) {// y[i].v = v[i] - x*w[i];// y[i].index = i+1;// }// double sum = 0;// sort(y, y+n);// for( int i = 0; i < k; i++ ) {// sum += y[i].v;// }// return sum >= 0;//}////void solve() {// double low = 0;// double high = INF;// for( int i = 0; i < 100; i++ ) {// double m = (low + high) * 0.5;// if( ok(m) ) {// low = m;// }// else {// high = m;// }// }// for( int i = 0; i < k; i++ ) {// if( i == 0 ) printf( "%d", y[i].index );// else printf( " %d", y[i].index );// }// printf( "\n" );//}////int main() {// while( scanf( "%d%d", &n, &k ) == 2 ) {// for( int i = 0; i < n; i++ ) {// scanf( "%lf%lf", v+i, w+i );// }// solve();// }// return 0;//}#include #include #include #include #include #include #include #include #include #include #include #include #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define mem0(a) memset(a,0,sizeof(a))#define sca(x) scanf("%d",&x)#define de printf("=======\n")typedef long long ll;using namespace std;const double INF = 20000000.0;const int maxn = 1e5+10;int n, k;struct node { double v; int index;}y[maxn];double v[maxn], w[maxn];int cmp( node n1, node n2 ) { return n1.v > n2.v;}bool ok( double x ) { for( int i = 0; i < n; i++ ) { y[i].v = v[i] - x*w[i]; y[i].index = i+1; } double sum = 0; sort(y, y+n, cmp); for( int i = 0; i < k; i++ ) { sum += y[i].v; } return sum >= 0;}void solve() { double low = 0; double high = INF; for( int i = 0; i < 50; i++ ) {// while( high - low > 1e-8 ) { double m = (low + high) * 0.5; if( ok(m) ) { low = m; } else { high = m; } }}int main() { while( scanf( "%d%d", &n, &k ) == 2 ) { for( int i = 0; i < n; i++ ) { scanf( "%lf%lf", v+i, w+i ); } solve(); for( int i = 0; i < k; i++ ) { if( i == 0 ) printf( "%d", y[i].index ); else printf( " %d", y[i].index ); } printf( "\n" ); } return 0;}
思考： 这个题是二分， 自己的代码是不是又写搓了？ 哎， 二分专题就先到这里吧， 自己对于二分的总结就是： 将要求的那个值设出来， 再根据已知条件判断我们这个设出来的值是不是符合条件， 二分的不断得去逼近答案......这就是我做了这些二分题对于二分的一些思考， 我自己也会逐渐地去反思， 自己到底欠缺在哪里， 然后进步， 开下个专题然后去打比赛
转载于:https://www.cnblogs.com/FriskyPuppy/p/7488040.html
