CodeForces - 1324DPair of Topics
题目大意：
这题大意ai+aj>bi+bj全在这个式子上，就问你满足的组合有几种，
题目分析：
整理一下，得到(ai-bi)+(aj-bj)>0，所以现在我们就只用做个差，然后找有几种组合就好了，
开始比较笨，tle了一发，后来才知道要分治一下，我们给做差后的数组排个序，每次找到比自己大的第一个数的下标，那么就可以很快的得到可以有几种组合
AC代码：
#include<iostream>#include<cmath>#include <cstring>#include<stdio.h>#include<stdlib.h>#include<iostream>#include<string.h>#include<algorithm>using namespace std;const int maxn=1e6;long long s1[maxn],s=0,b=0,ans,a1[maxn],b1[maxn];int t;int main(){while(scanf("%d",&t)!=EOF){s=0;b=0;ans=0;for(long long i=1;i<=t;i++){scanf("%lld",&a1[i]);}for(long long i=1;i<=t;i++){scanf("%lld",&b1[i]);a1[i]-=b1[i];}sort(a1+1,a1+1+t);for(int i=1;i<=t;i++){long long cnt=upper_bound(a1+i+1,a1+t+1,-a1[i])-a1;//printf("%lld ",cnt);ans+=t-cnt+1;//printf("%lld\n",ans);}printf("%lld\n",ans);}}
我又有个问题：
现在问题解决了
当我数组下标从0开始的时候，upper_bound 返回的就不是第一个大于查询数的位置，而变成了大于等于，结果输出就不对了，这是为什么啊，
问题代码：
#include <cstring>#include<stdio.h>#include<stdlib.h>#include<iostream>#include<string.h>#include<algorithm>using namespace std;const int maxn=1e6;long long s1[maxn],s=0,b=0,ans,a1[maxn],b1[maxn];int t;int main(){while(scanf("%d",&t)!=EOF){s=0;b=0;ans=0;for(long long i=0;i<t;i++){scanf("%lld",&a1[i]);}for(long long i=0;i<t;i++){scanf("%lld",&b1[i]);a1[i]-=b1[i];}sort(a1,a1+t);for(int i=0;i<t;i++){long long cnt=upper_bound(a1+i,a1+t,-a1[i])-a1;printf("%lld ",cnt);ans+=t-cnt;printf("%lld\n",ans);//这里输出看看 }printf("%lld\n",ans),fflush(stdout);}}
这个，其实是我没注意，代码写错了，我传进upper_bound的是-a[o]比它大的是他自己没错，，所以注意：upper_bound(a1+i+1,a1+t+1,-a1[i])-a1这里查找的时候，其实是排除了它自己，如果下标从0开始，那么应该写成upper_bound(a1+i+1,a1+t,-a1[i])-a1，a1+1+i是从后一个开始查，但是a1+t就可以了，这是他的上界
所以修改后的从0开始的代码：
#include<iostream>#include<cmath>#include <cstring>#include<stdio.h>#include<stdlib.h>#include<iostream>#include<string.h>#include<algorithm>using namespace std;const int maxn=1e6;long long s1[maxn],s=0,b=0,ans,a1[maxn],b1[maxn];int t;int main(){while(scanf("%d",&t)!=EOF){s=0;b=0;ans=0;for(long long i=0;i<t;i++){scanf("%lld",&a1[i]);}for(long long i=0;i<t;i++){scanf("%lld",&b1[i]);a1[i]-=b1[i];}sort(a1,a1+t);for(int i=0;i<t;i++){long long cnt=upper_bound(a1+i+1,a1+t,-a1[i])-a1;//printf("%lld ",cnt);ans+=t-cnt;//printf("%lld\n",ans);//这里输出看看 }printf("%lld\n",ans),fflush(stdout);}}
