結果
問題 |
No.67 よくある棒を切る問題 (1)
|
ユーザー |
![]() |
提出日時 | 2019-01-01 14:41:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,142 bytes |
コンパイル時間 | 1,845 ms |
コンパイル使用メモリ | 166,096 KB |
実行使用メモリ | 9,884 KB |
最終ジャッジ日時 | 2025-03-03 11:20:37 |
合計ジャッジ時間 | 8,118 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 WA * 16 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n, k; cin >> n; vector< long double > l(n); for (int i=0; i<n; ++i) cin >> l[i]; cin >> k; auto check = [=](long double mid) { long double sm = 0; for (int i=0; i<n; ++i) // long doubleなので, 値を潰さないように sm += (floor)(l[i] / mid); return sm >= k; }; // [ok, ng) okはギリギリ満たす数, ngがギリギリ満たさない数 // そのうち, 満たす数の最大値を求めたい // ただし, 今回は小数が答えなので範囲を狭めることで解を求める // 1度二分探索をすると, 解の範囲は(1/2)になるので, // 10^10の範囲を10^-9以下(怖いので10^-10未満にします)にするためには, // log2(n) = (10^10)/(10^10) = 10^20を解いて, 大体n >= 67くらい? // まぁ100回も回せば十分でしょう long double ok = 0, ng = 1e10 + 1; for (int i=0; i<100; ++i) { long double mid = (ng+ok)/2; if (check(mid)) ok = mid; else ng = mid; } double ans = ok; cout << fixed << setprecision(10) << ans << endl; return 0; }