Table-with-Numbers#

题面#

Peter drew a table of size $h \times l$, filled with zeros. We will number its rows from $1$ to $h$ from top to bottom, and columns from $1$ to $l$ from left to right. Ned came up with an array of numbers $a_1, a_2, \ldots, a_n$ and wanted to modify the table.

Ned can choose $2k \leq n$ numbers from his array and split them into $k$ pairs. After that, for each resulting pair $x, y$, he takes the cell located in row $x$ and column $y$, and adds $1$ to the number in that cell. If such a cell does not exist, then this pair does nothing to the table.

Peter supported Ned’s initiative and asked him to maximize the sum of the numbers in the table. Help Ned understand what the maximum sum he can achieve is.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $h$, and $l$ ($2 \le n \le 100$, $1 \le h, l \le 1000$) — the size of the array, the height of the table, and the width of the table, respectively.

The second line of each test case contains $n$ numbers $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \le a_i \le 1000$) — the array itself.

Output

For each test case, output the maximum possible sum of the numbers in the table.

思路#

先把题目理清楚：

• 表格初始全是 $0$，每做一个有效配对 $(x,y)$（满足 $1\le x\le h,\ 1\le y\le l$），表格总和就 $+1$
• 所以题目本质是：最多能做出多少个有效配对

代码#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
int main() {
6
    ios::sync_with_stdio(false);
7
    cin.tie(nullptr);
8

9
    int t;
10
    cin >> t;
11
    while (t--) {
12
        int n, h, l;
13
        cin >> n >> h >> l;
14

15
        vector<int> a(n + 1);
16
        for (int i = 1; i <= n; i ++) cin >> a[i];
17

18
        long long both = 0, r = 0, c = 0;
19
        for (int i = 1; i <= n; i ++) {
20
            if (a[i] <= h && a[i] <= l) {
21
                both ++;
22
            } else if (a[i] <= h) {
23
                r ++;
24
            } else if (a[i] <= l) {
25
                c ++;
26
            }
27
        }
28

29
        long long ans = 0;
30

31
        long long cross = min(r, c);
32
        ans += cross;
33
        r -= cross;
34
        c -= cross;
35

36
        long long b = min(both, r + c);
37
        ans += b;
38
        both -= b;
39

40
        ans += both / 2;
41

42
        cout << ans << '\n';
43

44
    }
45

46
    return 0;
47
}