考前写题解 \(\rm rp++\)。
题目大意
给定 \(n\) 个数 \(a[1\cdots n]\) 问你满足 \(a[i]\times a[j]\times a[k]\) 的值最小，且 \(i<j<k\) 的有序对有几个？
题目分析
很妙的一道题。
来一个 \(\operatorname{O(n~log~n)}\) 的做法。
看到求三个数相乘的最小值，再看到 \(3\le n\le10^5\) 的数据范围，妥妥的 \(\log~n\) 啊！
可以马上想到将数组升序排列一遍，然后看整段序列有多少个数与 \(a[3]\) 相等，答案即为 \(tmp\)。
接下来分类讨论：
- 当 \(a[1]=a[2]=a[3]\) 时，直接在 \(tmp\) 里选 \(3\) 个数出来即可。
答案为
\[C_{tmp}^3 \] \[=\dfrac{tmp!}{(tmp-3)!\times 3!} \] \[=\dfrac{tmp\times(tmp-1)\times(tmp-2)\times\cdots\times 2\times1}{(tmp-3)\times(tmp-4)\times\cdots\times2\times1\times3\times2\times1} \] \[=\dfrac{tmp\times(tmp-1)\times(tmp-2)}{3\times2\times1} \]- 当 \(a[1]\neq a[2]\) 但 \(a[2]=a[3]\) 时，第一个必然应该选择，剩下的就从 \(tmp\) 中选 \(2\) 个出来即可。
答案为
\[C_{tmp}^2 \] \[=\dfrac{tmp!}{(tmp-2)!\times2!} \] \[=\dfrac{tmp\times(tmp-1)}{2\times1} \]- 其他情况。
这个时候，前两个数必然应该选择，剩下一个数直接在 \(tmp\) 里任意选 \(1\) 个即可。
故此时输出 \(tmp\)。
代码
const int ma=100005;
int a[ma];
int n;
#undef int
int main(void)
{
#define int long long
n=read();
for(register int i=1;i<=n;i++)
{
a[i]=read();
}
sort(a+1,a+n+1);
int tmp=0;
for(register int i=1;i<=n;i++)
{
if(a[i]==a[3])
{
tmp++;
}
}
if(a[1]==a[2] && a[2]==a[3])
{
printf("%lld\n",tmp*(tmp-1)*(tmp-2)/(3*2*1));
}
else if(a[2]==a[3])
{
printf("%lld\n",tmp*(tmp-1)/2);
}
else
{
printf("%lld\n",tmp);
}
return 0;
}
你看我熬夜写的这么认真，不点个赞吗 \(\mathcal{QwQ}\)。