yukicoder No.67 よくある棒を切る問題(1)
感想
長さを二分探索したけど、で回すと大きい数の時、無限ループしてしまいました。
なので適当に100回ぐらいで打ち切った。
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef pair<int,pair<int,int>> PP; typedef long long ll; const double EPS = 1e-10; const int INF = 1e9; const int MOD = 1e9+7; int dy[] = {0,1,0,-1}; int dx[] = {1,0,-1,0}; struct edge{int to,cost,tm;}; bool func(double len,ll K,vector<int>&L){ ll cnt = 0; for(int i=0;i<L.size();i++){ cnt += L[i]/len; if(cnt >= K)return true; } return false; } int main(void) { ll N,K; cin >> N; vector<int> L(N); for(int i=0;i<N;i++){ cin >> L[i]; } cin >> K; double low=0,hi=1e9,mid=0; int t = 0; while(hi > low+EPS && t < 100){ mid = (low + hi)/2; if(func(mid,K,L)){ low = mid; }else{ hi = mid; } t++; } cout << fixed << setprecision(11) << low << endl; return 0; }
double値の二分探索初めてした気がする。
無限ループに陥らないように気をつけていきたいです。