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; }
最后
以上就是独特歌曲最近收集整理的关于CodeForces - 1324 D. Pair of Topics 思维+多解法的全部内容,更多相关CodeForces内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复