【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c942
【解題想法】二分搜
- 測資保證每個圓都至少有一個露營點，因此各點之間的環狀距離的最大值為「最小圓周長」，最小值為 0。
- 二分搜找出符合題意（可以規劃M個露營點數）的環狀距離。
#include <iostream>
#include <cmath>
using namespace std;
#define PI atan(1)*4.0
int N, M;
int R[11];
bool check(double m){
int sum = 0;
for (int i = 0; i < N; i++){
sum += (int)((R[i] * 2.0 * PI) / m);
}
return sum >= M;
}
int main() {
while (cin >> N >> M){
if (N == 0 && M == 0) break;
int mn = 0x7FFFFFFF;
for (int i = 0; i < N; i++){
cin >> R[i];
mn = min(mn, R[i]);
}
double l = 0.0;
double r = 2.0 * PI * mn;
double ans = 0.0;
while (r - l > 0.01){
double m = (l + r) / 2.0;
if (check(m)){
ans = m;
l = m;
} else {
r = m;
}
}
for (int i = 0; i < N; i++){
cout << (int)(2.0 * PI * R[i] / ans) << " ";
}
cout << "\n";
}
return 0;
}
Python code (credit: Amy Chou)
import math
def check(m):
return sum([2 * math.pi * r // m for r in R]) >= M
while True:
N, M = map(int, input().split())
if N == 0 and M == 0:
break
R = list(map(int, input().split()))
l = 0
r = 2 * math.pi * min(R)
ans = 0
while r - l > 0.01:
m = (l + r) / 2
if check(m):
ans = m
l = m
else:
r = m
for i in range(N):
print(f"{2*math.pi*R[i]//ans:.0f} ", end="")
print()