[codeforces 1324D] Pair of Topics 分而治之+排列组合

Codeforces Round #627 (Div. 3)   比赛人数6434

[codeforces 1324C]  Frog Jumps   一直向右+边界处理

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

也在线测评地址http://codeforces.com/contest/1324/problem/D

第一次能在比赛中AC掉D题，虽然是Div. 3的难度，但也是可喜可贺。从AC的时间上看，离比赛结束只有2分零几秒。

上一场比赛，要是多给5分钟，就能在上一场的Div. 2比赛中AC掉D题了。

涨码力了。

该题的突破公式ai+aj>bi+bj变换一下，变成(ai-bi)+(aj-bj)>0，就这么一变换，算法就呼之欲出。怎么想到的？

当时是这样的，计算ai+aj，bi+bj觉得对应着O(n^2)的算法，就想着，作差试试，于是就一发不可收拾，想到了对应的算法。

将差值分为a-b>0,a-b<=0两组进行讨论。

手工算法如下

Input:
5
4 8 2 6 2
4 5 4 1 3
Output:
7
a
4 8
2
6
2
b
4 5
4
1
3
a-b 0 3 -2
5 -1
a-b>0
3 5
a-b<=0
-2 -1 0
可能的组合(3,5),(3,-2),(3,-1),(3,0),(5,-2),(5,-1),(5,0)
可以这样考虑
a-b>0 3 5有2个数据，选2个，C(2,2)=1
a-b<=0的数据取绝对值，对绝对值，自小到大排序0,1,2
0<3,可以配对
1<3,可以配对
2<3,可以配对
与3可以配对的情况有3种，
因5>3,与3可以配对的，一定可以与5配对，就不要重复计算了。该题与５可以配对的情况有3种，
答案为1+3+3=7

#include <cstdio>
#include <algorithm>
#define LL long long
#define maxn 200010
using namespace std;
int a[maxn],b[maxn],bn,c[maxn],cn;
int main(){
int n,i,j;
LL ans=0;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)scanf("%d",&b[i]);
for(i=1;i<=n;i++)a[i]-=b[i];
sort(a+1,a+1+n);
for(i=1;i<=n;i++)
if(a[i]<=0)b[++bn]=a[i];//b[]存储差值<=0
else c[++cn]=a[i];//c[]存储差值>0
ans+=(LL)cn*(cn-1)/2;//正数集合里随便选
j=1;
for(i=1;i<=bn;i++)b[i]=-b[i];//对非正数集合取绝对值
sort(b+1,b+1+bn);//绝对值按自小到大排列
for(i=1;i<=bn;i++){
while(j<=cn&&b[i]>=c[j])j++,ans+=(i-1);//i-1之前数据包括i-1位置的数据都可以与c[j]配对
if(j>cn)break;//正数集合处理完毕
}
if(j>cn)printf("%lldn",ans);
else{
ans+=(LL)bn*(cn-j+1);//正数集合中剩下数据的处理
printf("%lldn",ans);
}
return 0;
}

最后

以上就是多情狗为你收集整理的[codeforces 1324D] Pair of Topics 分而治之+排列组合的全部内容，希望文章能够帮你解决[codeforces 1324D] Pair of Topics 分而治之+排列组合所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。