【題解】ZeroJudge c942: 露營區規劃

【題目敘述】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()
分享本文 Share with friends