D. Pair of Topics（构造+排序+优化处理）Codeforces Round #627 (Div. 3)

原理链接： https://codeforces.com/problemset/problem/1324/D

测试样例：

Input
5
4 8 2 6 2
4 5 4 1 3
Output
7
Input
4
1 3 2 4
1 3 2 4
Output
0

题意： 给定长度为n的a数组和b数组，如果$a_i+a_j>b_i+b_j$ai​+aj​>bi​+bj​，其中$1\leq i <j\leq n$1≤i<j≤n，那么这样的组队方案成为好方案，请问有多少个这样的方案。

解题思路： 对于这个问题，很好理解，用暴力方法做最让人舒服了，可是TLE也是必然的。那么，如果不能用暴力，我们就要想一下其他的方法了，我们这样看这个表达式，将式子全部移到左端变为:$a_i-b_i+a_j-b_j>0$ai​−bi​+aj​−bj​>0，化到这里，我们就会想到构建方法了，我们用$c_i$ci​表示$a_i-b_i$ai​−bi​，那么我们即是要判断$c_i+c_j>0$ci​+cj​>0的组数。可你是不是还会认为，这样是不是还要暴力解决。当然不必，我们对我们新构建的数组$c$c进行排序，那么我们发现我们只要记录第一个和最后一个元素的位置，再都往中间移即可，即若最后一个能够能第一个配对，那么也能和第二个第三个配对。那么这种配对方法我们就过完了，剔除最后一个。 我们就会去找倒数第二个，若倒数第二个不能和第一个配对，那么说明倒数第三个等等的也不能和此配对，我们同样剔除。（我这里只是随便列出几种情况距离）这样判断过去即可，知道最后一个元素和第一个元素过到一起，说明没有可选择的对数了。那么此题就可以解决了，时间复杂度为$O(n)$O(n)。

AC代码：

/*
*邮箱：[e-mail]
*blog:https://me.csdn.net/hzf0701
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*
*/
#include<bits/stdc++.h>	//POJ不支持

#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int inf = 0x3f3f3f3f;//无穷大
const int maxn = 2e5+2;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************分割线，以上为自定义代码模板***************************************//

int n;
ll a[maxn],b[maxn];
int main(){
	//freopen("in.txt", "r", stdin);//提交的时候要注释掉
	IOS;
	while(cin>>n){
		rep(i,1,n){
			cin>>a[i];
		}
		rep(i,1,n){
			cin>>b[i];
			a[i]-=b[i];
		}
		sort(a+1,a+1+n); //获取差值，利用我们得到的公式a[i]-b[i]+a[j]-b[j]>0.
		int flag=1,cnt=n;
		ll ans=0;
		while(1){
			if(flag==cnt)break;
			if(a[flag]+a[cnt]>0){ //若当前第一个和最后一个能配对成组
				ans+=(cnt-flag);  //那么第一个之后的也必能，这种个数为cnt-flag
				cnt--;// 剔除最后一个
			}
			else{
				//若不能，说明当前第一个和最后一个前面的也必不能配对成功，则剔除第一个。
				flag++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}