题目链接

上方题目链接。

 

题目大意：给一个n*4的矩阵，从每一列里选出一个数，问有多少中算法，令选出来的4个数和为0。

题目思路：这道题刚开始以为用暴搜，n*n*n*n这难免会超时，所以对自己的思路产生了怀疑，这道题除了这种解法还有别的解法嘛？

1.没有了（至少在我的能力范围内），然后我便开始 想办法 优化，因为 题目 只求 和为0，所以我们不需要有别的顾虑，所以我们可以 把前两列和先算出来，再把后两列不同的和算出来，存到两个数组里：

void Star()
{
    tot1=0,tot2=0;
    for(int i=1;i<=n;i++)
        for(int k=1;k<=n;k++)
            sum1[++tot1]=num[i][1]+num[k][2];//num是开始的储存数组
    for(int i=1;i<=n;i++)
        for(int k=1;k<=n;k++)
            sum2[++tot2]=num[i][3]+num[k][4];
}

或许这里就有人会问，也可以先把 三列任意任意元素和存起来然后再和最后一列任意元素和相加只要是0就可以：

我们来比较一下复杂度：

 第一种情况 :2*n^2  第二种情况:n^3

显然第二种情况费时间，我们现在也没有其他办法只好选择最优。

2.我们来看一下现在的复杂度，分数组复杂度为2*n^2，在把两个数组之间 每一个元素对应相加 判断是否为0:

void calculate()
{
    for(int i=1;i<=tot1;i++)
        for(int k=1;k<=tot2;k++)
            if(sum1[i]+sum2[i]==0)
                 ans++:
}

tot1,tot2分别时 两个数组的大小，其实我们可以算出来，tot1=tot2=n*n。

所以这样就成了 n^4，优化了一圈又回到了原点。

3.但是这个思路有没有用呢？有用，我们想一下这个时间 多余在哪 ，其实就是最后一步的判断，我们需要判断每一个 sum1与sum2比较是否为0。所以说我们只需要优化这一个地方：判断sum1+sum2=0.

4.sum1+sum2=0也就是说 sum1=-sum2。所以我们思路改变为 找sum1 与 sum2[i] 成相反数的有多少个：意思就是 每一个sum2[i]都找在sum1中找一个-sum2[i]，其实就是 找 -sum2[i] 在sum1中有多少个。

5.这样也可以枚举，sort排序一下，然后找到一个-sum2[i]的位置，找到最后一个sum2[i]位置，之间有多少个也就清楚了。

复杂度 O(nlgn+tot1*tot2)，因为你每一次遍历sum数组找最小的， 所以这种还是不可以。

6.这里(敲重点)便出现了二分的应用：求 一个数 在一段序列中出现的次数。

我们首先二分查找第一个大于等于x的数，其次再查找第一个大于x的数，他们两个位置之差就是x出现的个数。

比如说一段序列 1 2 2 4，第一个大于等于x的数位置 2，第一个大于x的数 位置 4，cnt=4-2=2。并且这种复杂度时log复杂度。

7.所以这个题目也就解决了，写一下二分然后 对应每一个 sum2[i]就好了，不过现在的复杂度是(2*n*n+2*nlgn+lgn^2*n^2),这种复杂度已经对于这个题来说已经是极限了叭(在我范围之内)，因为就算n^2=2^64long long界限这个值才是64，速度非常的快。

所以这个题目解决，唯一不同的是，这里需要用到STL里面C++的二分函数：upper_bound && lower_bound

因为我用之前写过的二分教超时了，而用STL教却没有超时，希望这里有大神可以指点我一下。

现在附上代码 就可以了：

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod=10007;
const int INF=0x3f3f3f3f;
const int maxn=1e6+5;
ll num[4005][4005];
ll sum1[4005*4005];
ll sum2[4005*4005];
int n;
ll tot1,tot2;
ll ans=0;
void Star()
{
    tot1=0,tot2=0;
    for(int i=1;i<=n;i++)
        for(int k=1;k<=n;k++)
            sum1[++tot1]=num[i][1]+num[k][2];
    for(int i=1;i<=n;i++)
        for(int k=1;k<=n;k++)
            sum2[++tot2]=num[i][3]+num[k][4];
    sort(sum1+1,sum1+1+tot1);
    sort(sum2+1,sum2+1+tot2);
}
ll Cal(ll x)
{
    ll temp=upper_bound(sum1+1,sum1+tot1+1,x)-lower_bound(sum1+1,sum1+1+tot1,x);//代码下方 有这两个函数的使用
    return temp;
}
void solved()
{
    for(int i=1;i<=tot2;i++)
        ans+=Cal(-sum2[i]);//枚举每一个sum2[i]
    printf("%lld\n",ans);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int k=1;k<=4;k++)
            scanf("%lld",&num[i][k]);
    Star();
    solved();
    return 0;
}

既然用到STL里面的 upper_bound&&lower_bound，那现在也补充一下也算对我的一个复习(因为这两个用法相同，那就一个来说明)：upper_bound(begin,end,x)，从begin开始到end结束，左闭右开查找第一个大于x的数，找到就返回该元素地址，否则返回末尾地址，这里注意如果要输出一个位置 需要 返回的地址-起始地址。

总结：

之前遇到过二分的题目是 最大最小值，最小最大值，而现在二分又可以多解决一种问题，序列中 x出现的次数。

二分与很多东西都可以连用，所以我们可以慢慢积累，慢慢使用，加油!