結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー qwewe
提出日時 2025-05-14 13:07:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,813 bytes
コンパイル時間 960 ms
コンパイル使用メモリ 99,956 KB
実行使用メモリ 11,940 KB
最終ジャッジ日時 2025-05-14 13:09:36
合計ジャッジ時間 13,664 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <iomanip>

// Use long double for calculations involving the length X to ensure high precision.
using Real = long double; 

/**
 * @brief Check function to determine if it's possible to obtain at least K pieces of length X.
 * 
 * Given N sticks with lengths L_i, determines if we can cut them to obtain at least K pieces,
 * each of length exactly X. This is possible if the sum of floor(L_i / X) over all sticks is >= K.
 * 
 * @param X The target length of the pieces. Must be positive.
 * @param K The required minimum number of pieces. Must be >= 1.
 * @param N The total number of initial sticks.
 * @param L A const reference to the vector containing the lengths of the N sticks.
 * @return true If it's possible to obtain at least K pieces of length X.
 * @return false Otherwise.
 */
bool can(Real X, long long K, int N, const std::vector<long long>& L) {
    // If X is effectively zero or negative, handle appropriately.
    // Since K >= 1, we need a positive length X.
    // A very small positive X allows cutting potentially infinite pieces from any stick of positive length.
    // Using 1e-18 as a threshold for "practically zero". Choose a value smaller than required precision.
    if (X <= 1e-18) { 
         // If K>=1, we can always achieve it with tiny X as long as there is at least one stick with L_i > 0.
         // Since problem constraints state L_i >= 1, this is always true.
         return true;
    }

    long long current_pieces = 0; // Accumulator for the total number of pieces obtained.

    // Iterate through all sticks
    for (int i = 0; i < N; ++i) {
        // Calculate the number of pieces of length X obtainable from the current stick L[i].
        // Use long double for the division to maintain precision.
        // floor function correctly handles cases: returns 0 if L[i] < X.
        Real pieces_ld = floor((Real)L[i] / X);

        // Optimization: Check if this single stick provides enough pieces.
        // K can be up to 5e5. pieces_ld could potentially be very large if X is tiny.
        // If pieces_ld >= K, we have already met the requirement.
        if (pieces_ld >= K) {
             current_pieces = K; // Set current_pieces to K to indicate success (or more than K)
             break; // Exit loop early as we have enough pieces
        }
        
        // Since pieces_ld < K, it's guaranteed to be less than 5e5.
        // This value safely fits within a long long. Cast it.
        long long pieces_ll = (long long)pieces_ld;
        
        // Add the pieces obtained from this stick to the total count.
        // To prevent potential overflow (though unlikely with K <= 5e5), 
        // check if adding pieces_ll would reach or exceed the remaining needed pieces (K - current_pieces).
        if (K - current_pieces <= pieces_ll) { 
            current_pieces = K; // Cap total pieces at K, indicates success
            break; // Exit loop early
        }
        
        // Otherwise, add the pieces and continue to the next stick.
        current_pieces += pieces_ll;
    }
    
    // After checking all sticks (or breaking early), return true if we gathered at least K pieces.
    return current_pieces >= K;
}

int main() {
    // Use fast I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N; // Number of sticks
    std::cin >> N;
    std::vector<long long> L(N); // Vector to store stick lengths
    long long max_L = 0; // Keep track of the maximum stick length
    
    // Read stick lengths and find the maximum length
    for (int i = 0; i < N; ++i) {
        std::cin >> L[i];
        if (L[i] > max_L) {
            max_L = L[i];
        }
    }

    int Q; // Number of queries
    std::cin >> Q;
    
    // Set output precision to satisfy the problem requirement (e.g., 1e-9 error tolerance)
    // 17 decimal places is usually sufficient for typical competitive programming tasks needing high precision.
    std::cout << std::fixed << std::setprecision(17); 

    // Process each query
    for (int i = 0; i < Q; ++i) {
        long long K_query; // Required number of pieces for this query
        std::cin >> K_query;
        
        // Set up binary search range for the maximum possible length X.
        // The length X can range from 0 up to the maximum stick length.
        // We use [0, max_L + 1.0] as the search interval. max_L + 1.0 ensures that max_L is potentially included.
        Real low = 0.0, high = max_L + 1.0; 
        
        // Perform binary search for a fixed number of iterations.
        // 100 iterations reduce the search interval size by a factor of 2^100, 
        // which provides extremely high precision, well beyond typical requirements like 1e-9.
        for (int iter = 0; iter < 100; ++iter) {
            // Calculate midpoint safely to avoid potential overflow if low and high were large
            Real mid = low + (high - low) / 2.0; 
            
            // Check if it's possible to obtain K_query pieces of length `mid`
            if (can(mid, K_query, N, L)) {
                // If yes, `mid` is a possible length. The maximum possible length could be `mid` or even larger.
                // So, we update the lower bound of our search range to `mid`.
                low = mid;
            } else {
                // If no, `mid` is too long. The maximum possible length must be smaller than `mid`.
                // So, we update the upper bound of our search range to `mid`.
                high = mid;
            }
        }
        
        // After 100 iterations, `low` converges to the maximum possible length X that satisfies the condition.
        std::cout << low << "\n";
    }

    return 0;
}
0