I Tried to Write A Solution for this Problem.

1618D - Array and Operations

Observation

1. When performing an operation where $$$a_i = a_j$$$, the score will increase by 1, because if $$$a_i \equiv x$$$, then:

On the other hand, when performing an operation where $$$a_i \neq a_j$$$, the score will minimally increase by 0, because if $$$a_i < a_j$$$, then:

and vice versa.

1. Exactly $$$k$$$ operations will be performed on an array of $$$n$$$ integers, where each operation increases the score according to the rule in point 1. Additionally, there are $$$n - (2 \cdot k)$$$ integers that will be added to the score without any special operation. Thus, $$$\boxed{2 \cdot k}$$$ numbers undergo operations, and $$$\boxed{n - (2\cdot k)}$$$ numbers do not.

Steps

1. Sort the array in ascending order.

2. Add $$$ \displaystyle{\sum_{i = 1}^{n-2\cdot k}a_i}$$$ to the score. I believe this is correct because $$$n - 2 \cdot k$$$ numbers without operations should be taken from the beginning of the sorted array to minimize the score addition (proof unknown). The next step is to exhaust the remaining numbers in the array with special operations, where the remaining numbers are guaranteed to be even in count.

3. The final step is to increase the score using special operations. The main goal of this step is to pair each number, ensuring: as much as possible, avoid pairing the same number to minimize the score increase to 0 (following the rule in Observation point 1).

Conjecture for Step 3

Example of an array after Step 2: [1, 1, 1, 1, 2, 3]
Optimal pairing: [1, 2], [1, 3], [1, 1]

From the example above, the conjecture can be stated as:

where $$$f =$$$ frequency of a number.

For the example above, the frequencies are:
$$$1:4$$$, $$$2:1$$$, $$$3:1$$$.

Proof for Step 3

There are three critical variables:
- $$$m = f_{max}$$$
- $$$t = f_{total} - f_{max}$$$
- $$$g = \frac{m + t}{2}$$$

Note:
- $$$m =$$$ number of occurrences of the number with the maximum frequency.
- $$$t =$$$ total frequency of all numbers except for the number with the maximum frequency.
- $$$g =$$$ total groups formed, where each group contains 2 numbers.

If $$$m > t$$$: the maximum frequency of a number exceeds the total frequency of other numbers. This means there are cases where a number is paired with itself. Why can this happen?
I recall the pigeonhole principle from discrete mathematics. The number of pigeonholes is $$$g$$$, and there are $$$m + t$$$ pigeons entering the pigeonholes in order, starting with $$$m$$$ followed by $$$t$$$. The same number will end up in the same pigeonhole if $$$m > g$$$.

Since $$$m > g$$$ and each pigeonhole already contains one pigeon of value $$$f_{max}$$$, there are $$$m - g$$$ pigeons that will fly to the pigeonholes already containing a pigeon of the same value. It is then to be added to the score.

Remaining pigeons entering will not affect the score, as they are of different values.

Proof if $$$m \leq t \Rightarrow \text{score} = \text{score} + 0$$$

This visualization does not use pigeonholes but instead uses rows of 2.
The grouping is organized as:
$$$row_1, column_i$$$ with $$$row_2, column_i$$$.

Example grouping for the array [1, 1, 1, 1, 2, 3]:
$$$ \boxed{1} \boxed{1} \boxed{1} $$$
$$$ \boxed{1} \boxed{2} \boxed{3} $$$

Example of grouping when $$$m = 4\;and\; t = 6:$$$
$$$ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{y} $$$
$$$ \boxed{y} \ \boxed{z} \ \boxed{z} \ \boxed{a} \ \boxed{b} $$$
where $$$x$$$ is the maximum frequency.

If $$$m = t$$$, then the grouping will look like this:
$$$ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{x} $$$
$$$ \boxed{y} \ \boxed{y} \ \boxed{y} \ \boxed{z} $$$
The first row will always contain $$$m$$$ and the second row will contain $$$t$$$. \ Thus, each group will always have different pairs.
Score does not increase.

If $$$m < t$$$, then

Since $$$m < g \Rightarrow$$$ the construction of the first row will have leftover space for placing $$$t$$$ (all m is to be constructed first).
$$$ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{?} $$$
$$$ \boxed{?} \ \boxed{?} \ \boxed{?} \ \boxed{?} $$$

There will be numbers grouped with the same numbers if and only if there is a number from the first row that meets again in the second row as shown in the following example.
$$$ \boxed{x} \ \boxed{x} \ \boxed{x} \ \boxed{y} $$$
$$$ \boxed{y} \ \boxed{y} \ \boxed{y} \ \boxed{y} $$$

However, this cannot happen because the following condition cannot be met:

where $$$y$$$ is the frequency of one of $$$t$$$.
Since $$$m < g$$$ and $$$y \leq m$$$, we have

Score does not increase.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

#define debug 0 
#define fastio ios::sync_with_stdio(false); cin.tie(nullptr)
using namespace std;
int const LIMIT = 2 * 1e5 + 1;

int main() {
    fastio;

    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;
        
        vector<int> arr(n);
        for (auto &x : arr) cin >> x;

        sort(arr.begin(), arr.end());

        int score = 0;
        int ptr = 0;
        for (int i = 0; i < n - k * 2; i++) {
            score += arr[ptr];
            ptr++;
        }
        if (debug) cout << "pointer now " << ptr << endl;

        vector<int> cnt(LIMIT);
        for (; ptr < n; ptr++) {
            cnt[arr[ptr]]++;
        }

        int max_idx = 0;
        int total = 0;
        for (int i = 0; i < LIMIT; i++) {
            if (cnt[i] > cnt[max_idx]) {
                max_idx = i;
            }
            total += cnt[i];
        } 
        
        total -= cnt[max_idx];
        if (cnt[max_idx] > total) {
            score += (cnt[max_idx] - total) / 2;
        }

        cout << score << endl;
    }
    return 0;
}