Paired Up

Solución

Explicación

En la entrada de ejemplo, tenemos las siguientes vacas: $8, 5, 5, 2$ , y hay dos formas de emparejarlas.

$(8, 5), (5, 2)$
$(8, 2), (5, 5)$

El primer caso tomaría $13$ unidades de tiempo para terminar de ordeñar a todas las vacas.

El segundo caso tomaría $10$ unidades de tiempo para terminar de ordeñar a todas las vacas.

Este caso de prueba consiste en 3 valores distintos: $8, 5, 2$ , llamémoslos $A, B, C$ . Seguirían el paradigma $A < B < C$ .

Por lo tanto, $A+C < B + C$ .

Siempre deberíamos emparejar el valor más grande ( $C$ ) con el valor más pequeño ( $A$ ), para lograr el tiempo de ordeño más óptimo.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

(Porque requiere ordenar la entrada, que es $\mathcal{O}(N\log N)$ ).

C++PythonJava


#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
 
typedef pair<int, int> pii;
 
int main() {
	ifstream fin("pairup.in");
	ofstream fout("pairup.out");
	int N;
	vector<pii> V;
	fin >> N;
	for (int i = 0; i < N; i++) {
		int num_cows, milk_time;
		fin >> num_cows >> milk_time;
		V.push_back(pii(milk_time, num_cows));
	}
	sort(V.begin(), V.end());
	int M = 0, left = 0, right = N - 1;
 
	while (left <= right) {
		// la cantidad máxima de vacas que podemos agrupar.
		int sub = min(V[left].second, V[right].second);
		if (left == right) sub /= 2;
		M = max(M, V[left].first + V[right].first);
		V[left].second -= sub;
		V[right].second -= sub;
 
		// cuando no quedan más vacas disponibles en nuestro
		// par, podemos incrementar/decrementar el/los puntero(s)
		// izquierdo/derecho.
		if (V[left].second == 0) left++;
		if (V[right].second == 0) right--;
	}
	fout << M << "\n";
}


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])
 
all_cows.sort()
left, right = 0, n - 1
ans = 0
 
while left <= right:
	# cuántas vacas se agruparon.
	sub = min(all_cows[left][1], all_cows[right][1])
	ans = max(ans, all_cows[left][0] + all_cows[right][0])
	if left == right:
		sub /= 2
	all_cows[left][1] -= sub
	all_cows[right][1] -= sub
	# Si no quedan más vacas con esta producción de leche,
	# podemos incrementar/decrementar el puntero izquierdo/derecho.
	if all_cows[left][1] == 0:
		left += 1
	if all_cows[right][1] == 0:
		right -= 1
 
print(ans)


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());
			int freq = Integer.parseInt(tok.nextToken());
			int amt = Integer.parseInt(tok.nextToken());
			events.add(new Pair(freq, amt));
		}
 
		Collections.sort(events);
		int ret = 0;
		int left = 0, right = N - 1;
		while (left <= right) {
			// cuántas vacas se agruparon.
			int numPaired = Integer.min(events.get(left).freq, events.get(right).freq);
			if (left == right) { numPaired /= 2; }
			ret = Integer.max(ret, events.get(left).amt + events.get(right).amt);
			events.get(left).freq -= numPaired;
			events.get(right).freq -= numPaired;
 
			// Si no quedan más vacas con esta producción de leche,
			// podemos incrementar/decrementar el puntero izquierdo/derecho.
			if (events.get(left).freq == 0) { left++; }
			if (events.get(right).freq == 0) { right--; }
		}
		PrintWriter out = new PrintWriter(new FileWriter("pairup.out"));
		out.println(ret);
		out.close();
	}
}
 
class Pair implements Comparable<Pair> {
	public int freq, amt;
 
	public Pair(int freq, int amt) {
		this.freq = freq;
		this.amt = amt;
	}
	public int compareTo(Pair other) { return Integer.compare(this.amt, other.amt); }
}

Solución en video

Nota: La solución en video podría no ser la misma que las otras soluciones. Código en C++.

Video de YouTube (yIoUWlzH_7w)

Código de la solución en video

Implementación

Complejidad temporal: $\mathcal{O} (N \log N)$

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ifstream cin("pairup.in");
	ofstream cout("pairup.out");
 
	int n;
	cin >> n;
 
	vector<pair<int, int>> cows(n);
	for (int i = 0; i < n; i++) { cin >> cows[i].first >> cows[i].second; }
 
	sort(begin(cows), end(cows), [&](auto &a, auto &b) { return a.second < b.second; });
 
	int curr_l = 0, count_l = 0;
	int curr_r = n - 1, count_r = 0;
	int ans = 0;
 
	while (curr_l <= curr_r) {
		ans = max(ans, cows[curr_l].second + cows[curr_r].second);
		count_l++, count_r++;
 
		if (count_l > cows[curr_l].first) {
			curr_l++;
			count_l = 0;
		}
		if (count_r > cows[curr_r].first) {
			curr_r--;
			count_r = 0;
		}
	}
 
	cout << ans << '\n';
}


import java.io.*;
import java.util.*;
 
public class PairUp {
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio("pairup");
 
		int n = io.nextInt();
		int[][] cows = new int[n][2];
		for (int i = 0; i < n; i++) {
			cows[i][0] = io.nextInt();
			cows[i][1] = io.nextInt();
		}
 
		Arrays.sort(cows, (a, b) -> a[1] - b[1]);
 
		int currL = 0, countL = 0;
		int currR = n - 1, countR = 0;
		int ans = 0;
 
		while (currL <= currR) {
			ans = Math.max(ans, cows[currL][1] + cows[currR][1]);
			countL++;
			countR++;
 
			if (countL > cows[currL][0]) {
				currL++;
				countL = 0;
			}
			if (countR > cows[currR][0]) {
				currR--;
				countR = 0;
			}
		}
 
		io.println(ans);
		io.close();
	}
 
	// CodeSnip{Kattio}
}