Test/Algorithms/BinarySearch_double_rev.test.cpp

• View this file on GitHub
• Last update: 2024-12-27 17:36:05+09:00
• Problem: https://yukicoder.me/problems/no/67

Depends on

• Library/Algorithms/BinarySearch.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/67"
#define ERROR "1e-9"

#include <iomanip>

#include <iostream>

#include <vector>


#include "./../../Library/Algorithms/BinarySearch.hpp"


using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';
struct Preprocessing {
  Preprocessing() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);
  };
} _Preprocessing;

signed main() {
  ll n;
  cin >> n;
  std::vector<ll> a(n);
  for (int i = 0; i < n; ++i) { cin >> a[i]; }
  ll k;
  cin >> k;

  auto ans = mtd::binarySearch(1e-9, 1e9, 100, [&](double mid) {
    ll count = 0;
    for (const auto& x : a) { count += (1.0 * x / mid); }
    return count >= k;
  });

  cout << std::fixed << std::setprecision(12) << ans << endl;
}

#line 1 "Test/Algorithms/BinarySearch_double_rev.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/67"
#define ERROR "1e-9"

#include <iomanip>

#include <iostream>

#include <vector>


#line 2 "Library/Algorithms/BinarySearch.hpp"

#include <concepts>

#include <numeric>

#include <ranges>

#include <type_traits>


namespace mtd {

  template <class Lambda>
  auto binarySearch(double ok, double ng, int rep, const Lambda& is_ok) {
    for ([[maybe_unused]] auto _ : std::views::iota(0, rep)) {
      double mid = (ok + ng) / 2.0;
      (is_ok(mid) ? ok : ng) = mid;
    }
    return ok;
  }

  template <class Lambda, std::integral T1, std::integral T2>
  auto binarySearch(T1 ok_, T2 ng_, const Lambda& is_ok) {
    using T = std::common_type_t<T1, T2>;
    T ok = ok_, ng = ng_;
    while (std::abs(ok - ng) > 1) {
      T mid = (ok + ng) >> 1;
      (is_ok(mid) ? ok : ng) = mid;
    }
    return ok;
  }

}  // namespace mtd

#line 9 "Test/Algorithms/BinarySearch_double_rev.test.cpp"

using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';
struct Preprocessing {
  Preprocessing() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);
  };
} _Preprocessing;

signed main() {
  ll n;
  cin >> n;
  std::vector<ll> a(n);
  for (int i = 0; i < n; ++i) { cin >> a[i]; }
  ll k;
  cin >> k;

  auto ans = mtd::binarySearch(1e-9, 1e9, 100, [&](double mid) {
    ll count = 0;
    for (const auto& x : a) { count += (1.0 * x / mid); }
    return count >= k;
  });

  cout << std::fixed << std::setprecision(12) << ans << endl;
}

Back to top page