CF1166C
题意
给你n个数,从中选两个数,一个作为x,一个作为y,要求
min(|x-y|,|x+y|)<=|x|,|y|<=max(|x-y|,|x+y|)求满足条件的(x,y)的对数,(x,y)和(y,x)视作一种.
$2<=n<=2e5$
$-1e9<=a_i<=1e9$
思路
这个题其实大力讨论也是可以的,讨论之后二分即可,但是很繁琐,还容易出错.
在观看题解之后,才意识到居然可以这么做:
| 首先,对于合法的(x,y) ,(-x,y)也是可以满足的,更广泛的来讲,**只要( | x | , | y | )满足,那么 (x,y)就一定满足** |
简单证明一下:
| 如果( | x | , | y | )满足,则一定有min(|x-y|,|x+y|)<=|x|,|y|<=max(|x-y|,|x+y|) ,而|x-y|==|y-x| |
将x=-x代入,则会得到两个新式子|y-x|=>|y+x|,|y+x|=>|y-x| 对比上个长式子,我们发现这个不会影响正确性(因为只是最大值和最小值交换了一下值而已).
| 所以**只要( | x | , | y | )满足,那么 (x,y)就一定满足** |
证明了这个之后,剩下的问题就迎刃而解了.
我们在存数的时候,直接存绝对值就好.对于x>=0,y>=0的情况,自然有(此处假设x稍小)x+y>=y>=x>=y-x
也就是只要x>=y-x成立,则等式就一定能成立,也就是y>=x && 2*x>=y
我们对数组排序,然后从小到大遍历,对于遍历到的x,我们二分从数组中找到合适的y,进行计算.
复杂度$O(nlogn)$
AC代码
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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[200000 + 100];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
a[i] = abs(a[i]);
}
sort(a, a + n);
ll ans = 0ll;
int r = 0;
for (int i = 0; i < n; ++i) {
ans += upper_bound(a, a + n, 2 * a[i]) - a - i - 1;
}
// 实际上由于单调性的问题,也就是最后求的r一定不会向左移动,所以这里可以O(n)解决此问题
// for (int i = 0; i < n; ++i) {
// while (r < n && a[r] <= 2 * a[i])
// ++r;
// ans += r - i - 1;
// }
cout << ans << endl;
return 0;
}
