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;
}
|