Algorithm

We could translate the problem into
$$\begin{align} \max\ \ & \sum_{j=1}^{k}P_{i_{j}}\\ \text{subject to}\ \ & P_{i_{j}}\geq W_{i_{j}}\text{ and }\frac{P_{i_{j}}}{P_{i_{k}}}=\frac{Q_{i_{j}}}{Q_{i_{k}}}\text{ for all }(j,k), \end{align}$$
where $i_{j}$ denotes the subsequence indices and $P_{i_{j}}$ denotes the actual payments to worker $i$. First, we note that for any optimal solution set $\mathrm{OPT=}\{P_{i_{1}},…,P_{i_{k}}\},$ there exists at least one $P_{i_{j}}\in\mathrm{OPT}$ such that $P_{i_{j}}=W_{i_{j}},$ because otherwise we can exchange $P_{i_{j}}$ with $W_{i_{j}}$ and recompute the whole set and achieve a better result.

On the other hand, notice that we can rewrite our objective as $$\sum_{j=1}^{k}P_{i_{j}}=\sum_{j=1}^{k}\frac{P_{i_{j}}}{Q_{i_{j}}}Q_{i_{j}}.$$ This suggests that we can compute all $\frac{W_{i}}{Q_{i}}$’s and hope to search for an efficient algorithm using the order of $\frac{W_{i}}{Q_{i}}$’s we just computed.

Lemma 1. Suppose we pay worker $i$ the minimum wage $W_{i}$, then within the contraint for all worker $j$ with $\frac{W_{j}}{Q_{j}}>\frac{W_{i}}{Q_{i}}$, the actualy payment will be less than the minimum wage, i.e. $P_{j}<W_{j}.$

Proof. Note that by the constraint, we have $$\frac{P_{i}}{P_{j}}=\frac{Q_{i}}{Q_{j}}\implies P_{j}=P_{i}\cdot\frac{Q_{j}}{Q_{i}}=\frac{W_{i}}{Q_{i}}\cdot\frac{Q_{j}}{W_{j}}\cdot W_{j}=\frac{W_{i}/Q_{i}}{W_{j}/Q_{j}}\cdot W_{j}<W_{j},$$ and we are done.

An easy corollary of the previous lemma is the following:

Corollary 1. Suppose we pay worker $i$ the minimum wage $W_{i}$, then within the constraint for all worker $j$ with $W_{j}/Q_{j}\leq W_{i}/Q_{i}$, the actual payment will be higher than the minimum wage, i.e. $P_{j}>W_{j}.$

So the algorithm is then clear:

1. For each worker $i,$ compute $W_{i}/Q_{i}$ and find $K-1$ workers whose $W/Q$ does not exceed $W_{i}/Q_{i}$ and calculate the actual payout. The final answer is the minimum of all candidates.

2. To speed up, we can greedily select the $K-1$ workers whose $Q$ value is as low as possible. This is because the final payout of worker $j\neq i$ is $P_{j}=\frac{W_{i}}{Q_{i}}Q_{j}.$ Thus, minimizing $Q_{j}$ will minimize $P_{j}$.

3. To achive (2), we can use a priority queue to keep track of the lowest $Q_{j}.$ We specialize this queue to a new type bounded_priority_queue. This structure supports

   1. Maintain $k$ lowest value of in an linear input stream.
   2. Query the fold of $k$(upto) lowest values over a group structure.

Code

template <typename T> struct addition_group {
  typedef T value_type;
  value_type unit() const { return T{0}; }
  value_type mult(value_type a, value_type b) const { return a + b; }
  value_type inv(value_type a) const { return T{-1} * a; }
};


template <class value_type, typename Group = std::tuple<>, class Compare = std::less<value_type>>
class bounded_priority_queue {
 private:
  template <typename> struct is_tuple: std::false_type {};
  template <typename ...T> struct is_tuple<std::tuple<T...>>: std::true_type {};

 private:
  static constexpr auto group_ = Group{};
  static constexpr auto has_group_structure_ = not is_tuple<Group>::value;
  std::priority_queue<value_type, std::vector<value_type>, Compare> pq_;
  std::size_t capacity_;
  value_type acc_pq_;

 public:
  bounded_priority_queue(std::size_t n) : pq_{}, acc_pq_{}, capacity_{n} {}
  bounded_priority_queue(std::size_t n, Compare comp) : pq_(comp), acc_pq_{}, capacity_{n} {}

  std::size_t size() const { return pq_.size(); }
  std::size_t capacity() const { return capacity_; }
  /* @ O(\log N) */
  void push(value_type item) {
    pq_.push(item);
    if constexpr (has_group_structure_) acc_pq_ = group_.mult(acc_pq_, item);
    if (std::size(pq_) == capacity_ + 1) {
      if constexpr (has_group_structure_) acc_pq_ = group_.mult(acc_pq_, group_.inv(pq_.top()));
      pq_.pop();
    }
  }
  /* @ O(1) */
  void pop() { pq_.pop(); };
  /* @ O(1) */
  value_type top() const { return pq_.top(); }
  /* @ O(1) */
  value_type reduce() const {
    if constexpr (has_group_structure_)
      return acc_pq_;
    else
      throw std::domain_error("does not have group structure");
  }
};

class Solution {
 public:
  double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
    const auto n = size(quality);

    struct worker_t {
      double Q;
      double W;
    };

    const auto sorted_workers = [&](vector<worker_t> self = {}) {
      for (int i = 0; i < n; ++i)
        self.emplace_back(worker_t{quality[i], wage[i]});
      std::sort(begin(self), end(self), [&](auto & x, auto &y) {
        return (x.W / x.Q) < (y.W / y.Q);
      });
      return self;
    }();


    const auto solution = [&](double acc = INT_MAX) {
      auto Q = bounded_priority_queue<double, addition_group<double>>(K);
      for (const auto [q, w] : sorted_workers) {
        Q.push(q);
        if (size(Q) == K) 
          acc = std::min(acc, w / q * Q.reduce());
      }
      return acc;
    }();

    return solution;
  }
};