Skip to Content
CTRL K

Ferris Wheel

Editorial no oficial 

Como cada góndola puede contener 1 o 2 niños, para cada góndola podemos hacer una de estas dos cosas:

  1. Emparejar al niño más liviano con el más pesado posible sin exceder el límite de peso.
  2. Si el emparejamiento no es posible, incluir solo al niño más liviano.

Los que queden sin emparejar tienen cada uno su propia góndola. La implementación de abajo usa el método anterior.

Como alternativa, para cada góndola también podemos

  1. Emparejar al niño más pesado con el más liviano si es posible.
  2. En caso contrario, incluir solo al niño más pesado.

Ambos métodos de emparejamiento se pueden lograr en O(n)\mathcal{O}(n) usando dos punteros, y el ordenamiento lleva la complejidad temporal total a O(nlog⁡n)\mathcal{O}(n\log n).

Implementación

Complejidad temporal: O(nlog⁡n)\mathcal{O}(n\log n)

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 2e5 + 10;
 
// Variables used for the current problem
int n, x, p[maxn], i, j, ans;
// Keeps track of the number of children who have had their own gondola
bool have_gondola_yet[maxn];
 
void solve() {
	cin >> n >> x;
	for (int i = 0; i < n; ++i) cin >> p[i];
	sort(p, p + n);
	i = 0;
	j = n - 1;
	while (i < j) {
		if (p[i] + p[j] > x) {
			// If the total weight of two children exceeds x
			// Then we move to the lighter child.
			--j;
		} else {    // If it satisfies the condition.
			++ans;  // Increment the number of gondolas used
			// Mark that they have had their gondola
			have_gondola_yet[i] = have_gondola_yet[j] = true;
			++i;
			--j;  // Move to the next children.
		}
	}
	for (int i = 0; i < n; ++i) {
		// Calculate the number of children not having gondolas yet
		// to get the total number of gondolas needed for the problem.
		ans += have_gondola_yet[i] == false;
	}
	cout << ans << "\n";
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
	return 0;
}
import java.util.*;
 
public class FerrisWheel {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
 
		int n = sc.nextInt();
		int x = sc.nextInt();
		sc.nextLine();
 
		// Read in weights of children (this optimization is necessary to pass
		// all test cases)
		String[] weightsStr = sc.nextLine().split(" ");
		// weights is of type Integer to prevent having to cast the result from
		// Integer.parseInt() to an int, saving time (part of optimization)
		Integer[] weights = new Integer[n];
		for (int i = 0; i < n; i++) { weights[i] = Integer.parseInt(weightsStr[i]); }
		Arrays.sort(weights);
 
		int ans = 0;
		int i = 0;      // left pointer
		int j = n - 1;  // right pointer
		while (i <= j) {
			ans++;  // Increment number of gondolas used
			if (i == j) break;
			// If total weight is too large, move to lighter child
			if (weights[i] + weights[j] > x) {
				j--;
			}
			// Otherwise, we pair the two children and move on
			else {
				i++;
				j--;
			}
		}
		System.out.println(ans);
	}
}
_, max_weight = map(int, input().split())
weights = sorted(map(int, input().split()))
 
light_ptr = 0
heavy_ptr = len(weights) - 1
gondola_total = 0
while light_ptr <= heavy_ptr:
	# Pair the heaviest child with the lightest child if possible
	if weights[light_ptr] + weights[heavy_ptr] <= max_weight:
		light_ptr += 1
		heavy_ptr -= 1
	# Otherwise, only include the heaviest child
	else:
		heavy_ptr -= 1
	# Increment the number of gondolas used
	gondola_total += 1
print(gondola_total)
Fundamentos