結果
問題 | No.67 よくある棒を切る問題 (1) |
ユーザー |
|
提出日時 | 2022-05-06 18:07:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 194 ms / 5,000 ms |
コード長 | 1,941 bytes |
コンパイル時間 | 2,054 ms |
コンパイル使用メモリ | 195,488 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-03-03 11:58:22 |
合計ジャッジ時間 | 7,343 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
// 相対誤差に応じて二分探索を終了できるように改良 // とりあえず、doulbe 型のみの対応 // もっと整理しました #include <bits/stdc++.h> using namespace std; using ll = long long; const int INF = (int)1e9 + 1001010; const ll llINF = (ll)4e18 + 11000010; #define ALL(x) x.begin(),x.end() #define RALL(x) x.rbegin(),x.rend() ll ceil(ll a, ll b){return (a+b-1) / b;}; // ================================== ここまでテンプレ ================================== // とある条件を満たす区間の境界を見つける // 探索区間は [ok, ng) または (ng, ok] // ok はつねに「とある条件」を満たす // ng はつねに「とある条件」を満たさない // 「とある条件」を満たすかどうかは、judge関数によって求められる template<class Judgement> double Binary_Search(double ok, double ng, Judgement judge, double tolerance, bool considerRelativeError = false){ auto need_continue = [&]() -> bool{ if((fabs(ok - ng) > tolerance)) return false; // 絶対誤差 if(considerRelativeError && (fabs(ok - ng) > tolerance * fabs((ok + ng) * 0.5))) return false; // 相対誤差 return true; }; while((fabs(ok - ng) > tolerance) && (fabs(ok - ng) > tolerance * fabs((ok + ng) * 0.5))){ // while(need_continue()){ double mid = (ok + ng) * 0.5; if(judge(mid)) ok = mid; else ng = mid; } return ok; }; int main(){ int n; cin >> n; vector<double> l(n); for(int i = 0; i < n; i++) cin >> l[i]; ll k; cin >> k; auto judge = [&](double mid) -> bool{ if(mid <= 0) return true; ll count = 0; for(int i = 0; i < n; i++){ count += floor(l[i] / mid); if(count >= k) return true; } return false; }; double ans = Binary_Search(-1.0, 1e12, judge, 1e-10); printf("%.12lf\n", ans); return 0; }