POJ 2976

题目地址:http://poj.org/problem?id=2976

题目大意

给$n$组数据$a_i, b_i$,定义累计平均值为:
$$100\cdot \dfrac{\sum_{i=1}^n a_i}{\sum_{i=1}^n b_i}$$

现给出一个整数$k$,要求从这$n$个数中去掉$k$个数后,最大累计平均值能有多大?(四舍五入到整数)

思路

其实就是问,取$n-k$个数,使得累计平均值最大。

那么,定义$C(x)$表示能否取得$n-k$个数,使得累计平均值$\geq x$。然后二分搜索最大的$x$。

可以这样判断可行性:

$$ \begin{aligned} \because & 100\cdot \dfrac{\sum_{i\in S} a_i}{\sum_{i\in S} b_i} \geq x \\ &\Leftrightarrow \sum_{i\in S} (100\cdot a_i) \geq \sum_{i\in S}(x\cdot b_i)\\ &\Leftrightarrow \sum_{i\in S}(100\cdot a_i - x\cdot b_i)\geq 0\\ &\Leftrightarrow sum \geq 0\\ \end{aligned}$$

$\therefore$ 只需要从大到小选取$n-k$个$(100\cdot a_i - x\cdot b_i)$并求和$sum$,根据$sum\geq 0$来判断(上述的$S$表示$n-k$个元素下标的集合)

AC代码

/*************************************************************************
    > File Name: 2976.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-23 三 18:23:16 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

typedef long long ll;
int n, k;
ll a[1000+4], b[1000+4];
double c[1000+4];

bool C(double x) { // 检验取出的n-k个数的累计平均值是否能>=x
    for(int i=0; i<n; ++i)    c[i] = a[i]*100 - x*b[i];
    sort(c, c+n);
    double sum = 0;
    for(int i=0; i<n-k; ++i) sum+=c[n-i-1];
    // printf("sum: %f\n", sum);
    return sum >= 0;
}

void solve() {
    double lb = 0, ub=1000000000000000.0;
    for(int i=0; i<100; ++i) { // 精度10e-30
        double mid = (ub + lb) /2.0;
        if(C(mid)) lb = mid; // 半闭半开区间[lb, ub)
        else ub = mid;
    }
    printf("%.f\n", floor(lb+0.5)); // 四舍五入
}

int main()
{
#ifdef Oj
    freopen("2976.in", "r", stdin);
#endif
    while(cin >> n >> k) {
        if(n==k && n==0) break;
        for(int i=0; i<n; ++i) cin >> a[i];
        for(int i=0; i<n; ++i) cin >> b[i];
        solve();
    }
    return 0;
}

POJ 3111

题目地址:http://poj.org/problem?id=3111

题目大意

给出$n$个珠宝的$v_i$和$w_i$,从中选出$k$个珠宝,使得$\dfrac{\sum_{i\in K} v_i}{\sum_{i\in K} w_i}$最大,求出这$k$个珠宝的序列。

思路

和上一题差不多,具体可看代码。这里只是要记录$K$个珠宝的序列。

AC代码

/*************************************************************************
    > File Name: 3111.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-23 三 20:12:00 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

const double EPS = 1e-6;

int n, k;
int v[100000+5], w[100000+5];
struct Remian{
    double c;
    int id;
    bool operator<(const Remian&b) const {
        return c > b.c;
    }
} remain[100000+5];

bool C(double x) {
    for(int i=0; i<n; ++i) {
        remain[i].c = v[i] - w[i]*x;
        remain[i].id = i+1; // 记录宝珠编号
    }
    sort(remain, remain+n);
    double sum = 0.0;
    for(int i=0; i<k; ++i) sum+=remain[i].c;
    return sum >= 0;
}

void solve() {
    double lb = 0.0, ub = 1000000000000000.0;
    while(ub - lb > EPS) { // 精度1e-6
    // for(int i=0; i<80; ++i) { // 精度10e-30
        double mid = (lb + ub) / 2.0;
        if(C(mid)) lb = mid; // 半闭半开区间[lb, ub)
        else ub = mid;
    }
    for(int i=0; i<k; ++i)    printf(i==0?"%d":" %d", remain[i].id);
    printf("\n");
}

int main()
{
#ifdef Oj
    freopen("3111.in", "r", stdin);
#endif
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; ++i) scanf("%d%d", &v[i], &w[i]);
    solve();
    return 0;
}