CodeForces - 1324 D. Pair of Topics 思维+多解法

156 阅读 0 评论 103 点赞

我是靠谱客的博主独特歌曲，这篇文章主要介绍CodeForces - 1324 D. Pair of Topics 思维+多解法，现在分享给大家，希望可以做个参考。

CodeForces - 1324 D. Pair of Topics

原题地址：

http://codeforces.com/contest/1324/problem/D

基本题意：

给你一个数组，找符合（i < j）ai + aj > bi + bj 的序列对的数量。

基本思路：

本质上我们设 ci = ai - bi 那么原式可以换为 ci + cj > 0，所以我们可以有几个思路：

pbds黑科技解法，我们转换为 cj > -ci 直接上红黑树每次插入 -ci 暴力往前找rank；

复制代码

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
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define INF 0x3f3f3f3f
typedef tree<pair<int,int>,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> rbtree;
const int maxn = 2e5 + 10;
int n,a[maxn],b[maxn];
int main() {
IO;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
ll ans = 0;
rbtree s;
for (int i = 0; i < n; i++) {
ans += s.order_of_key({a[i] - b[i], 0});
s.insert({b[i] - a[i], i});
}
cout << ans;
return 0;
}

关于pbds库的具体介绍可见：

https://www.luogu.com.cn/blog/Chanis/gnu-pbds

再附上一些rbtree操作资料：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
定义一颗红黑树
int 关键字类型
null_type无映射(低版本g++为null_mapped_type)
less<int>从小到大排序
rb_tree_tag 红黑树（splay_tree_tag）
tree_order_statistics_node_update结点更新
插入t.insert();
删除t.erase();
Rank:t.order_of_key();
第K值:t.find_by_order();
前驱:t.lower_bound();
后继t.upper_bound();
a.join(b)b并入a 前提是两棵树的key的取值范围不相交
a.split(v,b)key小于等于v的元素属于a，其余的属于b
T.lower_bound(x)
>=x的min的迭代器
T.upper_bound((x)
>x的min的迭代器
T.find_by_order(k) 有k个数比它小的数

离线 + 树状数组，具体代码不贴了，当时用这个过的，写了很久感觉自己很傻逼。

后面两个思路，我们先要想到，因为原式可以变换为 ci > - cj,和 cj > -ci, 所以原数组的顺序并不重要，即可以排序。

所以我们将数组c递增排序，要满足ci + cj > 0，我们从两边类似尺取，如果 c[l] + c[r] > 0 那么由于数组是递增排序的我们可以知道，c[ l --> (r - 1) ] + c[r] > 0 是一定的，这样向中间逼近就能得到答案；

复制代码

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
28
29
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)
for(int i = n ; i >= j ; i--)
#define INF 0x3f3f3f3f
const int maxn = 2e5 + 10;
int n,a[maxn],b[maxn],c[maxn];
signed main() {
IO;
cin >> n;
rep(i,1,n) cin >> a[i];
rep(i,1,n) cin >> b[i];
vector<int> vec;
rep(i,1,n) c[i] = a[i] - b[i];
sort(c+1,c+n+1);
int ans = 0;
int l = 1 , r = n;
while (true){
if(c[l] + c[r] > 0) ans += (r - l),r--;
else l++;
if(l == r) break;
}
cout << ans << endl;
return 0;
}

将数组c递增排序，变形一下原式为 -ci < cj，我们对于每个ci，往后直接二分查找大于 -ci 的数有多少个就可以了；

复制代码

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
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)
for(int i = n ; i >= j ; i--)
#define INF 0x3f3f3f3f
const int maxn = 2e5 + 10;
int n,a[maxn],b[maxn],c[maxn];
signed main() {
IO;
cin >> n;
rep(i,1,n) cin >> a[i];
rep(i,1,n) cin >> b[i];
rep(i,1,n) c[i] = a[i] - b[i];
sort(c+1,c+n+1);
int ans = 0;
rep(i,1,n){
int cnt = upper_bound(c+i+1,c+n+1,-c[i]) - c;
ans += n - cnt + 1;
}
cout << ans << endl;
return 0;
}