题目描述

难度分:$1400$

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

每组数据输入$n(3 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

你可以执行如下操作任意次：

• 选择$a$中的两个数$a[i]$和$a[j]$，把$a[i]$改成$a[j]$。

你需要把$a$变成好数组，即任意三个不同下标，对应的元素可以组成一个三角形（两边之和大于第三边）。输出最小操作次数。

输入样例

4
7
1 2 3 4 5 6 7
3
1 3 2
3
4 5 3
15
9 3 8 1 6 5 3 8 2 1 4 2 9 4 7

输出样例

3
1
0
8

算法

贪心

如果$a[i]$是最终数组的最大值，那么$\gt a[i]$的所有数都要被削成$a[i]$。而对于满足$a[j]+a[j+1] \leq a[i]$，前缀$[1,j]$的所有数也需要增涨至$a[j]$。

因此我们可以先对$a$排序，然后枚举最大值$a[i]$，二分得到最大的$j$，以及第一个大于$a[i]$的元素位置，就能得到以$a[i]$为最大值的情况下需要操作多少次。维护所有$i \in [1,n]$的操作次数最小值就是最终答案。

复杂度分析

时间复杂度

对$a$排序的时间复杂度为$O(nlog_2n)$；枚举$i$的时间复杂度为$O(n)$，但是每个$i$都需要进行两次二分查找（其实也可以用双指针做到$O(n)$，但是前面的排序已经$O(nlog_2n)$了，而且双指针我很容易写错，干脆就二分了），时间复杂度为$O(log_2n)$，因此这一步的时间复杂度也是$O(nlog_2n)$。算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

整个算法过程中只使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int T, n, a[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + n + 1);
        int ans = INT_MAX;
        for(int i = 3; i <= n; i++) {
            int ub = upper_bound(a + 1, a + n + 1, a[i]) - a;
            int l = 1, r = i - 2;
            while(l < r) {
                int mid = l + r + 1 >> 1;
                if(a[mid] + a[mid + 1] <= a[i]) {
                    l = mid;
                }else {
                    r = mid - 1;
                }
            }
            ans = min(ans, n - ub + 1 + (a[r] + a[r + 1] <= a[i]? r: 0));
        }
        printf("%d\n", ans);
    }
    return 0;
}