P9880 题解

liuyi0905 · 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;
}