洛谷题面
考前写题解 \(\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\)。
接下来分类讨论:
答案为
\[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} \]答案为
\[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}\)。