Description
给你 $n$ 个数，第 $i$ 个数为 $a_i$，现删去一些数后，将数两两配对，使它们的和都在 $l$ 到 $r$ 之间。问你最少要删多少个数。显然 $n$ 为偶数，答案也为偶数。
Solution
考虑如果 $(a, c)$ 和 $(b, d)$ 都是合法匹配对（其中 $a \leq b \leq c \leq d$），那么显然 $(a, d)$ 和 $(b, c)$ 都是合法匹配对。
然后考虑基于此的贪心。
将给定序列排序，得到 $a_1∼a_n$，然后记 $a_l$ 为当前最小的未确定是否保留的数，$a_r$ 为当前最大的未确定是否保留的数。
然后如果 $(a_l + a_r)$ 小于限制的下界，那么 $a_l$ 可以找到更好的那个 TA，删去 $a_l$。
如果 $(a_l + a_r)$ 在限制范围内，那么同时保留它们两个。
如果 $(a_l + a_r)$ 大于限制的上界，那么 $a_r$ 可以找到更好的那个 TA，删去 $a_r$。
如果算出来的答案是奇数的话那么强制加 1，使它变成偶数。
利用双指针可以做到 $O(n \log n + n)$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <cstdio>
#include <iostream>
#include <algorithm>
#define maxN 100010
using namespace std;
int a[maxN];
bool cmp (int x, int y)
{
return x < y;
}
int main ()
{
int n = 0, L = 0, R = 0;
scanf("%d %d %d", &n, &L, &R);
for(int i = 1;i <= n; i++)
{
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1, cmp);
int Ans = 0, l = 1, r = n;
while(l < r)
{
if(a[l] + a[r] < L)
{
l++, Ans++;
}
else if(a[l] + a[r] > R)
{
r--, Ans++;
}
else
{
l++, r--;
}
}
printf("%d", Ans + (Ans & 1));
return 0;
}
|