logoChat01.ai

The developers at Amazon are working on optimising...

作成日: 2025年9月5日

使用モデル GPT-5 by Chat01

質問

The developers at Amazon are working on optimising the enpacity of their cloud system. In the system.
there are n servers where the memory capacity of the ith server is represented by the array memorylil. A
system always contains an even number of servers. If the system has 2x servers, then x of them wili be
primary and the other x will be backup servers. For each primary server P. there exists a backup
server B where the memory capacity of B 2 memory capacity of P. The system's memory capacity is the
sum of the memory capacity of all the primary servers.

Given n servers and an array memory. find the maximum system memory capacity that can be formed
using the n servers.

Example
Given 5 servers as [serverA, serverB, serverC, serverD, serverE] having memory = [2, 4, 3, 1, 2].

In the second configuration, the system memory capecity is memory[serverA] + memory[serverD] = 3.
While in the third configuration, it is memoryserverA] + memory[serverC] = 5.
Hence, the maximum system memory capacity is 5.

Function Description
Complete the function maximumCapacity in the editor below.
maximumCapacity has the following parameter:
int memory[n]: the memory capacity of the given servers

Returns
long int: the maximum system memory capacity

Constraints
. 2<=n≤2* 10^5
· 1 <= size[i]≤ 10^9

Input:
4
1 2 1 2
Output: 3

Explanation
Here, we have 4 servers [serverA, serverB, serverC, serverD having memory sizes as [1, 2, 1, 2]. We
can choose serverA and serverB as primary servers, and serverC and serverD as their respective
backup. The conditions hold true since memory[serverC] ≥ memory[serverA] and memory[serverD] ≥
memorylserverB].
Hence, the meximum system memory capacity is 3.

Input:
3
1 2 1
Output: 1
Explanation
Here, we have 3 servers [serverA, serverB, serverC] having mernory sizes as [1, 2, 1] reepectively. We
can choose serverA as a primery server, and serverß as its reepective beckup server. The conditions
hold true since memory[serverB) 2 memorylserverAl.
Hence, the mædmum systemn memnory capecity ls 1.

long maximumcapacity(vector<int>memory){}

思考

Maximizing primary capacities

I need to solve a problem where there are n servers, and the system must pair them into primary-backup pairs. For each primary, the backup's capacity must be equal or greater, and I want to maximize the sum of the primes. So while the primary should be as large as possible, it must still fit the requirement that the backup’s capacity is equal to or greater.

Maximizing the sum of primaries

For each pair of servers, set the smaller as the primary and the larger as the backup. To maximize the sum, pair the servers such that each pair minimizes the difference while keeping the backup's capacity ≥ primary. The strategy seems to be sorting and pairing largest with second largest, but what if there's an odd number of servers? Would leaving the smallest unpaired be the best option?

Analyzing pairing strategies

When pairing servers from smallest to largest, the sum of the min values comes from odd-indexed servers. But when pairing from largest to smallest, the sum comes from even-indexed servers. It turns out that the sum of even-indexed elements is always greater or equal to the sum of odd-indexed elements. The largest-to-second-largest pairing maximizes the sum of mins, as it respects the primary being the smaller server and meets the requirement where backups ≥ primaries.

Maximizing sum of minima

This problem is a variation of the classic "maximize sum of minima" problem. The strategy is often to sort numbers in ascending order and pair adjacent elements. If there's an odd number of elements, it's best to drop the smallest and then pair adjacent ones. Testing with the example [2,4,3,1,2], sorting and discarding 1 leads to a sum of 4 from pairs (2,3) and (2,4).

Thought for 28s

回答

Here’s the idea: any valid system is formed by disjoint pairs (primary, backup) where backup ≥ primary. For a chosen pair, you should always label the smaller one as the primary (to satisfy the constraint). So the total capacity becomes the sum of the minima of all chosen pairs.

To maximize that sum:

  • Sort the array.
  • If n is even, pair adjacent elements from left to right → sum indices 0, 2, 4, …
  • If n is odd, leave the smallest element unused, then pair adjacent from there → sum indices 1, 3, 5, …

This is optimal because after sorting, pairing neighbors maximizes the sum of pairwise minima; with an odd count, discarding the smallest avoids dragging the sum down.

C++ implementation

cpp
#include <bits/stdc++.h>
using namespace std;

long long maximumcapacity(vector<int> memory) {
    sort(memory.begin(), memory.end());
    long long ans = 0;
    int n = (int)memory.size();

    // Start index: 0 if even n, 1 if odd n (skip the smallest when odd)
    int start = (n % 2 == 0) ? 0 : 1;

    for (int i = start; i + 1 < n; i += 2) {
        // Pair (memory[i], memory[i+1]); primary is memory[i]
        ans += (long long)memory[i];
    }
    return ans;
}

Quick checks

  • Input: 4 with 1 2 1 2 → sorted [1,1,2,2] → sum indices 0 and 2 → 1+2=3.
  • Input: 3 with 1 2 1 → sorted [1,1,2] (odd) → skip first, take index 1 → 1.

Time complexity: O(n log n) (sort). Space: O(1) extra (ignoring sort’s internal use).

このQ&Aを共有