POJ-3111 : K Best

問題概要

n(<10^5)個の商品があるので、K個選んで単位重みあたりの価値を最大化するように選ぶ問題。

解法

平均値について二分探索する。

acceptされたコード

#include
#include
#include
using namespace std;

const int MAX_N = (int)(1e5);

struct Item {
int value, weight, index;

Item(){}
Item(int value, int weight, int index):value(value), weight(weight), index(index){}
};

int N, K;
Item items[MAX_N];
double TEST;

bool operator> (const Item& lhs, const Item& rhs) {
return lhs.value - TEST * lhs.weight > rhs.value - TEST * rhs.weight;
}

void init() {
scanf("%d%d", &N, &K);
for (int i = 0; i < N; ++i) {
scanf("%d%d", &items[i].value, &items[i].weight);
items[i].index = i;
}
}

bool check() {
sort(items, items + N, greater());
double tmp = 0.0;
for (int i = 0; i < K; ++i) {
tmp += items[i].value - TEST * items[i].weight;
}
return tmp > 0;
}

void solve() {
double low = 0.0, high = 1e7;
for (int _ = 0; _ < 60; ++_) {
TEST = (low + high) * 0.5;
if (check()) {
low = TEST;
}
else {
high = TEST;
}
}
for (int i = 0; i < K; ++i) {
printf("%d%c", items[i].index + 1, i==K-1 ? '\n' : ' ');
}
}

int main() {
init();
solve();
return 0;
}
|