Greedy Algorithms

On the national holiday of country H, the king invited n ministers to play a game with prizes. First, he asked each minister to write an integer on each of their left and right hands, and the king himself also wrote an integer on each of his left and right hands. He then arranged the n ministers in a line, with the king standing at the very front of the line. After they were arranged, all ministers would receive some gold coins as a reward from the king. The reward received by each minister is the product of the numbers on the left hands of all people in front of that minister, divided by the number on that minister's right hand, with the result rounded down.

The king does not want any particular minister to receive an especially large reward, so he asks you to rearrange the order of the line so that the reward received by the minister with the largest reward is as small as possible. Note that the king's position is always at the front of the line.

Let the numbers on the left and right hands of the $i$-th minister after sorting be $a_i, b_i$, respectively. Consider deriving a greedy strategy using the adjacent-exchange method.

Let $s$ denote the product of all $a_i$ values of the people in front of the $i$-th minister. Then the reward received by the $i$-th minister is $\dfrac{s} {b_i}$, and the reward received by the $i + 1$-th minister is $\dfrac{s \cdot a_i} {b_{i+1}}$.

If the $i$-th and $i + 1$-th ministers are exchanged, the reward received by the current $i$-th minister is $\dfrac{s} {b_{i+1}}$, and the reward received by the current $i + 1$-th minister is $\dfrac{s \cdot a_{i+1}} {b_i}$.

The arrangement before the exchange is better if and only if

Extracting the common $s$ and reducing gives

Converting the fractions to integer expressions gives

In the implementation, we save the two input numbers in a struct and overload the operator:

struct uv {
  int a, b;

  bool operator<(const uv &x) const {
    return max(x.b, a * b) < max(b, x.a * x.b);
  }
};

John's workday starts at time $0$ and has $10^9$ units of time. At any unit of time, he can choose any one of the N jobs numbered $1$ through $N$, where $N(1 \leq N \leq 10^5)$. The deadline of job $i$ is $D_i(1 \leq D_i \leq 10^9)$, and its profit after completion is $P_i( 1\leq P_i\leq 10^9 )$. Given the job profits and deadlines, find the maximum profit John can obtain.

1. First assume that every job is done, sort all jobs by deadline, and add them to the queue;
2. When deciding whether to do job i, if its deadline satisfies the condition, compare it with the element having the smallest reward in the queue. If the reward of job i is higher (regret), then ans += a[i].p - q.top()．
   Use a priority queue (min-heap) to maintain the smallest element at the front of the queue.
3. When a[i].d<=q.size(), this can be understood as follows: from time 0 to time a[i].d, only a[i].d tasks can be done. If q.size()>=a[i].d, completing q.size() tasks takes at least a[i].d units of time, so when the profit of job i is relatively large, the smallest task should be swapped out of the priority queue.

C++

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

struct f {
  long long d;
  long long p;
} a[100005];

bool cmp(f A, f B) { return A.d < B.d; }

// Maintain the minimum value with a min-heap
priority_queue<long long, vector<long long>, greater<long long>> q;

int main() {
  long long n, i;
  cin >> n;
  for (i = 1; i <= n; i++) {
    cin >> a[i].d >> a[i].p;
  }
  sort(a + 1, a + n + 1, cmp);
  long long ans = 0;
  for (i = 1; i <= n; i++) {
    if (a[i].d <= (int)q.size()) {  // Past the deadline
      if (q.top() < a[i].p) {       // Regret
        ans += a[i].p - q.top();
        q.pop();
        q.push(a[i].p);
      }
    } else {  // Add directly to the queue
      ans += a[i].p;
      q.push(a[i].p);
    }
  }
  cout << ans << endl;
  return 0;
}

Python

from collections import defaultdict
from heapq import heappush, heappop

a = defaultdict(list)
for _ in range(int(input())):
    d, p = map(int, input().split())
    a[d].append(p)  # Store the profit for the corresponding time

ans = 0  # Record the total profit
q = []  # Maintain the minimum value with a min-heap
l = sorted(a.keys(), reverse=True)
for i, j in zip(l, l[1:] + [0]):
    for k in a.pop(i):
        heappush(q, ~k)
    for _ in range(i - j):
        if q:  # Take the job with the highest profit from the heap
            ans += ~heappop(q)
        else:  # Exit the loop when the heap is empty
            break
print(ans)

• Space complexity: when $n$ tasks are input, $n$ elements are used in the $a$ array, and in the worst case the priority queue stores $n$ elements, so the space complexity is $O(n)$.
• Time complexity: the time complexity of std::sort is $O(n\log n)$, and the time complexity of maintaining the priority queue is $O(n\log n)$. Therefore, the overall time complexity is $O(n\log n)$.