T7模考题解

经验分享区
1

这道题目显而易见不能暴力否则喜提 TLE25 别问我我是怎么知道的

我们需要更快的一个方法：

首先呢我们可以在输入的时候将数一样的存入同一个 map 里面。

然后呢我们需要遍历所有数值但是这里不能再暴力了，我们需要一个高效的数学方法来计算：

  • 我们求出两个数 sa 和 sb 其中 sb 表示这个位置作为右端点时，左边所有位置的值，sa 表示当前位置作为左端点时，右边所有位置的值，最后将 sb-sa 就是最后满足的三元数对。

放上有注释的伪代码：

   for(auto it:mp){
        auto res=it.second;//数字出现次数
        int m=res.size();
        if(m<2)continue;//如果没有重复则不可能实现
		int sa=0,sb=0;
        for(int i=0;i<m;i++)sb+=(res[i]-i)*i;//计算sb每次将左边位置的值加上
        for(int i=0;i<m;i++)sa+=(res[i]-i)*(m-1-i);//计算sa每次将右边位置的值加上
        ans+=sb-sa;//将其详见累加最后结果
    }

通过优化，我们就有效的将 O(N^2) 降为了 O(N) ！

3 个赞