CF1462E1【Close Tuples (easy version)】题解

# 组合数 [~~看不懂的~~题目传送门](https://www.luogu.com.cn/problem/CF1462E1) ### [博客食用 效果更佳](https://www.luogu.com.cn/blog/Rstar-PanzerTigerII/solution-cf1462e1) ------------ ## 分析 - 首先~~恶心人的~~是这是道纯英文的题的**题意**。借助@walk_alone dalao的题解，我们可以明白这题面的意思是 ：给定一个数组 $a$，取 $x \ ,y \ ,z\in a$ 满足 $x \ne y \ne z$，使得 $max(x \ ,y \ ,z) - min(x \ ,y\ ,z) \leqslant 2 $，问最多能找出多少组。 - 拿到题首先想的是 **`dfs`**，写了一个 $O(n^2)$ 的code 。当然对于一个 $2^5$ 的数据不 TLE 才怪。还好数据不算太强，勉强搞过几个点。 （随后听到机房大犇 @xspcz 在议论能不能用 **`map`** 存数据。但我不会啊……） - 最终在大犇们早都做完这题之后，我才感觉这题和组合数有些沾边（果然还是我太蒻了），于是想到了一个优雅的~~暴力~~算法。 什么？你不知道组合数？巧了，我[本来也不清楚，帮你度娘。](https://baike.baidu.com/item/%E7%BB%84%E5%90%88%E6%95%B0/2153250?fr=aladdin) - 本想一发 **`sort`** 之后从头开始求区间的组合，但是窝发现有问题，由于数据**可能重复**。 如数据 $1 \ 2 \ 3 \ 3 \ 4$，按上述方法就是答案计数器先加上 $1$ 和 $3$ 之间的组合数，求完之后再加上 $2$ ~ $4$ 之间的组合数，但是 $1$ ~ $3$ 之间的 $2 \ 3 \ 3$ 和 $2$ ~ $4$ 之间的 $2 \ 3 \ 3$ 重复了。~~于是卡了一节课 窝太菜了~~ - 后经学长点拨，在排序后先取一个值 $a[i]$，再在 $(a[i],a[i+2])$ 范围内取两个值，便可以避免重复。（妙哉！） 例如，求 $1$ ~ $3$ 时，取最小值 $1$，在 $(1,3]$ 区间内（即 $2 \ 3 \ 3$）任取两个值； 接着求 $2$ ~ $4$ 时，取最小值 $2$，在 $(2,4]$ 区间内任取两个值。 不难看出，以上情况无重复。 - 想清楚原理后就不难实现了 ------------ ## 实现 贴核心代码： ```cpp int t, /*anti-cheating*/ n; //本来想用桶，但后来想想没甚必要 int main(){ ios::sync_with_stdio(0);//加速cin、cout ，使其复杂度接近printf、scanf cin>>n; while(n--)｛ ll cnt=0;//！！！不开long long 见祖宗！！！ cin>>t; for(int i=1;i<=t;i++) cin>>ght[i]; sort(ght+1, ght+t+1);//排序数据以便枚举 int r=1; for(int i=1;i<=t;i++){ while(ght[r+1]<=2+ght[i] && r+1<=t） r++; if(r>=i+2) cnt+=(ll)(r-i-1)*(r-i);//！！被long long 卡死了一次 ！！ } cout<<cnt<<endl; } } ``` 满分17，目测已过。。 [Hard 版本](https://www.luogu.com.cn/problem/CF1462E2)就是将组合数的最大最小值之差改为了输入的数据，原理是一样的。 ## 重申一遍！！不开long long见祖宗！！！！！ ------------ [**没事的话，来我主页逛逛？**](https://www.luogu.com.cn/user/426545) 本蒟蒻为了防止图床炸掉重写本题解，望管理大大高抬贵手 :-）