yukicoder No.67 よくある棒を切る問題 (1)
問題
No.67 よくある棒を切る問題 (1) - yukicoder
N本の棒がある.
それらの棒を切ってK本の同じ長さの棒を取り出したいとき
そのK本の棒の最大の長さは幾つか.
解法
棒の長さの二分探索で解ける.
問題は誤差で,相対誤差または絶対誤差が以下ならよいので
二分探索の小さい方の値を,大きい方の値をとした時,
の時,終了すればいい.
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> using namespace std; #define RREP(i,s,e) for (i = s; i >= e; i--) #define rrep(i,n) RREP(i,n,0) #define REP(i,s,e) for (i = s; i < e; i++) #define rep(i,n) REP(i,0,n) #define INF 100000000 typedef long long ll; int main() { int i, n; double l, r; ll k; int L[200000]; cin >> n; rep (i,n) cin >> L[i]; cin >> k; l = 0; r = 1000000000; while (l+1e-9 < r && l*(1+1e-9) < r) { double m = (l+r) / 2; ll sum = 0; rep (i,n) sum += L[i]/m; if (sum < k) r = m; else l = m; } cout << fixed << setprecision(10) << r << endl; return 0; }
初め相対誤差がなんのことだかわからず,無限ループに陥ってしまっていた.