Pair of Topics-CF1324D
Ideas
Obviously, it is necessary to
a
i
+
a
j
>
b
i
+
b
j
a_i + a_j > b_i + b_j
ai? + aj?>bi? + bj? Simplify:
a
i
?
b
i
>
b
j
?
a
j
a_i – b_i > b_j – a_j
aibi?>bjaj?
a
i
?
b
i
>
?
(
a
j
?
b
j
)
a_i – b_i > -(a_j – b_j)
aibi?>?(ajbj?)
make
c
i
=
a
i
?
b
i
c_i = a_i – b_i
ci?=aibi?, then:
c
i
>
?
c
j
c_i > -c_j
ci?>?cj?
c
i
+
c
j
>
0
c_i + c_j > 0
ci? + cj?>0
What you want becomes:
satisfy
i
<
j
i < j
i
0
c_i + c_j > 0
ci? + cj?>0.
It can be seen that if there is no
i
<
j
i < j
i
0
c_i + c_j > 0
ci? + cj?>0, then sum it up.
In fact, we can find the answer using the above method
r
e
s
res
res and then execute
r
e
s
/
=
2
res~/=~2
res /= 2 is the constraint
i
<
j
i < j
Answer under i
c
i
c_i
When ci?, more calculations were made.
i
‘
>
j
‘
i’ > j’
i′>j′ and
c
i
‘
+
c
j
‘
>
0
c_i’ + c_j’ > 0
ci′? + cj′?>0, and such a pair
c
i
‘
,
c
j
‘
c_i’, c_j’
ci′?,cj′? in
i
(
in the process of traversing
i
)
=
j
‘
(
current
j
‘
)
i(i during traversal) = j'(current j’)
When i (i in the traversal process) = j′ (current j′), both conditions are satisfied at the same time. So the amount we calculate more is equal to the amount we should calculate, and ultimately
r
e
s
res
res divided by
2
2
2 is the correct answer to this question.
For example,
i
=
3
,
j
=
2
,
c
i
=
666
,
c
j
=
?
666
i = 3, j = 2, c_i = 666, c_j = -666
i=3,j=2,ci?=666,cj?=?666. When we use the method that has been used for hundreds of years, we will also take this situation into account. But if
i
,
j
i,j
i, j are swapped, we find
i
=
2
,
j
=
3
,
c
i
=
?
666
,
c
j
=
666
i = 2, j = 3, c_i = -666, c_j = 666
i=2,j=3,ci?=?666,cj?=666 satisfies two conditions at the same time. In the same way, every one that satisfies two conditions
i
,
j
i,j
Both i and j will
i
,
j
i,j
i, j after swapping
i
,
j
i,j
i, j will be incorrectly counted as correct cases.
C
o
d
e
Code
Code
#include <bits/stdc + + .h>
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;
int n;
int c[N];
void solve(int Case) {<!-- -->
cin >> n;
for (int i = 1; i <= n; i + + ) cin >> c[i];
for (int i = 1; i <= n; i + + ) {<!-- -->
int b; cin >> b;
c[i] -= b;
}
sort(c + 1, c + n + 1);
\t
int res = 0;
for (int i = 1; i <= n; i + + ) {<!-- -->
int l = 1, r = n;
while (l < r) {<!-- -->
int mid = (l + r) / 2;
if (c[i] + c[mid] > 0) {<!-- -->
r = mid;
} else {<!-- -->
l = mid + 1;
}
}
if (c[i] + c[l] > 0) {<!-- -->
res + = (n - l + 1) - (l <= i);
}
}
cout << " ";
cout << res / 2 << "\\
";
}
signed main() {<!-- -->
cin.tie(0)->ios::sync_with_stdio(false);
int T = 1;
// cin >> T; cin.get();
int Case = 0;
while ( + + Case <= T) solve(Case);
return 0;
}