本文主要是介绍【数学】Pair of Topics—CF1324D,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Pair of Topics—CF1324D
思路
很明显,需要对 a i + a j > b i + b j a_i + a_j > b_i + b_j ai+aj>bi+bj 化简:
a i − b i > b j − a j a_i - b_i > b_j - a_j ai−bi>bj−aj
a i − b i > − ( a j − b j ) a_i - b_i > -(a_j - b_j) ai−bi>−(aj−bj)
令 c i = a i − b i c_i = a_i - b_i ci=ai−bi,则:
c i > − c j c_i > -c_j ci>−cj
c i + c j > 0 c_i + c_j > 0 ci+cj>0
所求变成:
满足 i < j i < j i<j 且 c i + c j > 0 c_i + c_j > 0 ci+cj>0 的数量。
可以看出,如果没有 i < j i < j i<j 这个要求,那么我们可以对 c c c 排序,遍历 i i i,对于每一个 c i c_i ci 用二分求出满足 c i + c j > 0 c_i + c_j > 0 ci+cj>0 的数量,再求和即可。
其实我们恰恰可以上边的方法求出答案 r e s res res,然后再执行 r e s / = 2 res~/=~2 res /= 2 就是在约束条件 i < j i < j i<j 下的答案。
因为我们用这个方法遍历每一个 c i c_i ci 的时候,都多计算了其中 i ′ > j ′ i' > j' i′>j′ 且 c i ′ + c j ′ > 0 c_i' + c_j' > 0 ci′+cj′>0 的数量,而这样的一对 c i ′ , c j ′ c_i', c_j' ci′,cj′ 在 i ( 遍历过程中的 i ) = j ′ ( 当前的 j ′ ) i(遍历过程中的i) = j'(当前的j') i(遍历过程中的i)=j′(当前的j′) 时都是同时满足两个条件的。所以我们多计算的数量等于应该计算的数量,最终 r e s res res 除以 2 2 2 就是本题正确的答案。
例如, 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,我们在用上百年那个方法的时候会将这种情况也计算在内。但如果将 i , j i, j i,j 对调,我们发现 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 是同时满足两个条件的。同理,每一个满足两个条件的 i , j i, j i,j 都会其将 i , j i, j i,j 对调后的 i , j i, j i,j 都会错误地被当做正确情况计算在内。
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);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 << "\n";
}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;
}
这篇关于【数学】Pair of Topics—CF1324D的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!