結果
| 問題 |
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 |
ソースコード
#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;
}