【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c904
【解題想法】二分搜逼近求解
- <單位重量的售價> = <K 個蘋果的售價總和> / <K 個蘋果的重量總和>
- 設 <單位重量的售價> 的最大值為 x。
- x 最小可能值為 0（左界 L），最大可能值則趨近於無窮大（右界 R）
- 利用二分搜使中間值 m 逼近 x。
- 當 (v[0]+v[1]+…+v[K-1]) / (w[0]+w[1]+…+w[K-1]) >= m 時，往右界移動搜尋。
- 反之，往左界移動搜尋。
- 直到誤差小於 0.0001為止。
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
int N, M, K;
int w[1005], v[1005];
bool cmp(double x, double y){
return x > y;
}
bool check(double m){
double a[N];
for (int i = 0; i < N; i++){
a[i] = v[i] - m * w[i];
}
sort(a, a+N, cmp);
double sum = 0.0;
for (int i = 0; i < K; i++){
sum += a[i];
}
return sum >= 0.0;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++){
cin >> w[i] >> v[i];
}
while (M--){
cin >> K;
double L = 0.0;
double R = 1e18;
while (R - L > 0.0001){
double m = (L + R) / 2.0;
if (check(m)){
L = m;
} else {
R = m;
}
}
cout << fixed << setprecision(2) << L << "\n";
}
return 0;
}
Python code (credit: Amy Chou)
def check(m):
a = []
for i in range(N):
a.append(V[i] - m * W[i])
a.sort(reverse=True)
return sum(a[:K]) >= 0
N, M = map(int, input().split())
W = []
V = []
for _ in range(N):
w, v = map(int, input().split())
W.append(w)
V.append(v)
for _ in range(M):
K = int(input())
L = 0
R = 1e18
while R - L > 0.0001:
m = (L + R) / 2
if check(m):
L = m
else:
R = m
print(f"{L:.2f}")