题目描述

难度分:$1500$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$，$k(1 \leq k \leq 1000)$和长为$n$的数组$a(0 \leq a[i] \leq 10^9)$。保证$n$是偶数。

你需要把这$n$个数两两一对。把$a[i]$和$a[j]$组成一对的得分为$[\frac{a[i]+a[j]}{k}]$。

最大化这$\frac{n}{2}$个数对的得分之和，并输出这个最大值。

输入样例

6
6 3
3 2 7 1 4 8
4 3
2 1 5 6
4 12
0 0 0 0
2 1
1 1
6 10
2 0 0 5 9 4
6 5
5 3 8 6 3 2

输出样例

8
4
0
2
1
5

算法

双指针

不知道是不是没做惯的原因，总感觉$CF$的题目特别难做，每道题都感觉脑筋急转弯，难度分不高也要想好久。

对每个$a[i]$而言，一定可以为答案贡献$[\frac{a[i]}{k}]$（其中$[.]$表示对$.$向下取整），将所有的$[\frac{a[i]}{k}]$累加到答案上再让$a[i]$对$k$取模，$a$按照取模后的结果排序。

对于每个$a[i]$：

1. 如果$a[i]+a[j] \geq k$，那它们两个配对就可以再得一分；
2. 否则$a[i]+a[j] \lt k$，选择更小的$a[j]$是没有办法再得分的，只能往大了选。

这就有了单调性，指针不会回退，可以用相对双指针来为每个$a[i]$找到可以配对的$a[j]$。而为了得分效率更高，每次只要$a[i]$和$a[j]$可以配对，就马上配对。

复杂度分析

时间复杂度

算法的瓶颈在于对$a$数组排序，后续的双指针算法是$O(n)$的，因此算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间消耗也在于排序，以快速排序为基准，额外空间复杂度为$O(log_2n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;
typedef long long LL;

const int N = 200010;
int a[N], n, k;

LL solve() {
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += a[i] / k;
        a[i] %= k;
    }
    sort(a + 1, a + n + 1);
    for(int i = 1, j = n; i < j; i++) {
        if(a[i] + a[j] >= k) {
            j--;
            ans++;
        }
    }
    return ans;
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        printf("%lld\n", solve());
    }
    return 0;
}