#题解#洛谷P3143

[传送门](P3143 [USACO16OPEN] Diamond Collector S - 洛谷)

分析

解决问题只需枚举这样的两个组：使得每组中极差<=k，且两个组不交，求两个组元素

代码实现

#include<bits/stdc++.h>
using namespace std;
int k, n;
const int N = 1e5+10;
int a[N], q[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> k;for (int i = 1; i <= n; i++)cin >> a[i];sort(a + 1, a + 1 + n);for (int i = 1; i <= n; i++){int j = i;while (a[i] + k >= a[j] && j <= n)j++;q[i] = j;//[i,j-1]是为一组}int ans = -1;//枚举两个组for (int i = 1; i <= n; i++)for (int j = q[i]; j <= n; j++)ans = max(ans, q[i] - i + q[j] - j);cout << ans;return 0;
}

Trick/错误 总结

1.双指针查询一维数组的连续子段

2.ans中两组不交