自动搬运

查看原文

来自洛谷，原作者为

	liuyi0905 同学或橙名及以上且不fake私信互关

搬运于2025-08-24 22:52:40，当前版本为作者最后更新于2023-11-21 20:12:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

从序列中选出一对二元组 $(a,b)$，且 $a\times b<a+b$，求有几组满足条件的二元组。

首先考虑暴力解法，时间复杂度 $O(Tn^2)$，完全超时，所以只有可能是数学解法了。

众所周知，一个非正数乘一个正数一定小于两者之和，所以直接统计一下序列中负数和正数的个数，答案即为两者乘积。

代码：

cin>>n;
for(int i=1;i<=n;i++)cin>>x,x>0?z++:f++;
cout<<z*f<<"\n";

然后发现样例都没过

为何错了呢？

我们发现 $1$ 乘一个正数也小于两者之和，所以 $1$ 的个数也是需要额外统计的。输出就要改为：

cout<<z*f+v1*(z-v1)<<"\n";

然后发现又WA了

别忘了，如果序列中有多个 $1$，不同位置的 $1$ 也是可以匹配的，公式：

别忘了开 long long。

全部代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,x,z,f,v1;
signed main(){
	for(cin>>t;t;z=f=v1=0,t--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>x,x>0?z++:f++,v1+=x==1;
		cout<<z*f+v1*(z-v1)+v1*(v1-1)/2<<"\n";
	}
	return 0;
}