Official Analysis (C++)

Video Solution

Note: The video solution might not be the same as other solutions. Code in C++.

In the sample input, we have the following cows: $8, 5, 5, 2$, and there's two ways to pair these up.

1. $(8, 5), (5, 2)$
2. $(8, 2), (5, 5)$

The first case would take $13$ time units to finish milking all cows.

The second case would take $10$ time units to finish milking all cows.

This test case consists of 3 distinct values: $8, 5, 2$, let's call them $A, B, C$. These would follow the paradigm $A < B < C$.

Therefore, $A+C < B + C$.

We should always pair up the greatest value ($C$), with the smallest value ($A$), in order to achieve the most optimal milking time.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

(Because it requires sorting the input, which is $\mathcal{O}(N\log N)$).

Copy
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

typedef pair<int, int> pii;

int main() {

Copy
import sys

sys.stdin = open("pairup.in", "r")
sys.stdout = open("pairup.out", "w")

n = int(input())
all_cows = []
for _ in range(n):
	num_cows, milk_time = map(int, input().split())
	all_cows.append([milk_time, num_cows])

Copy
import java.io.*;
import java.util.*;

public class PairUp {
	public static void main(String[] args) throws IOException {
		BufferedReader io = new BufferedReader(new FileReader("pairup.in"));
		int N = Integer.parseInt(io.readLine().trim());
		List<Pair> events = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			StringTokenizer tok = new StringTokenizer(io.readLine());