题目描述
难度分:1400
输入T(≤104)表示T组数据。所有数据的n之和≤2×105。
每组数据输入n(3≤n≤2×105)和长为n的数组a(1≤a[i]≤109)。
你可以执行如下操作任意次:
- 选择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]是最终数组的最大值,那么>a[i]的所有数都要被削成a[i]。而对于满足a[j]+a[j+1]≤a[i],前缀[1,j]的所有数也需要增涨至a[j]。
因此我们可以先对a排序,然后枚举最大值a[i],二分得到最大的j,以及第一个大于a[i]的元素位置,就能得到以a[i]为最大值的情况下需要操作多少次。维护所有i∈[1,n]的操作次数最小值就是最终答案。
复杂度分析
时间复杂度
对a排序的时间复杂度为O(nlog2n);枚举i的时间复杂度为O(n),但是每个i都需要进行两次二分查找(其实也可以用双指针做到O(n),但是前面的排序已经O(nlog2n)了,而且双指针我很容易写错,干脆就二分了),时间复杂度为O(log2n),因此这一步的时间复杂度也是O(nlog2n)。算法整体的时间复杂度为O(nlog2n)。
空间复杂度
整个算法过程中只使用了有限几个变量,额外空间复杂度为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;
}