You need to enable JavaScript to run this app. 如何加速给定C++计数代码?附原循环实现与数学优化方案
优惠活动
大模型
产品
解决方案
定价
更多

如何加速给定C++计数代码?附原循环实现与数学优化方案

C++计数代码加速优化方案

需求说明

需要统计满足1<=i<=j<=n且j-i<=a的整数对总数量,参数取值范围为1<=n<=1000000,0<=a<=1000000。

原始实现的问题

最初的版本采用双层嵌套循环逐一遍历所有可能的i、j组合做条件判断,时间复杂度为O(n²),当n、a取值较大时运算量会快速膨胀,运行效率极低。
原始代码如下:

#include <iostream>
using namespace std;
int main(){
    int n, a, r = 0;
    cin>>n>>a;
    for(int i = 1; i <= n; i++){
        int j = i;
        for(j; j <= n; j++){
            if(j-i<=a){
                r++;
            }
        }
    }
    cout<<r;
}

优化思路

完全摒弃逐一枚举的循环逻辑,通过数学推导拆分场景直接计算结果,不需要遍历所有整数对,能把时间复杂度压到O(1),哪怕参数取到范围上限也能瞬时算出结果。
推导逻辑分场景判断:

  • 当a >= n时:所有满足1<=i<=j<=n的整数对自然符合j-i<=a的约束,总数量为等差数列和 n*(n+1)/2。
  • 当a < n时:将所有有效整数对拆为两部分求和:
    • i的取值范围在1 ~ n-a时,每个i可匹配的j范围为i ~ i+a,共a+1个合法值,这部分总对数为(n-a)*(a+1)
    • i的取值范围在n-a+1 ~ n时,每个i可匹配的j范围为i ~ n,对应的合法j数量从a递减到0,这部分总对数为等差数列和 a*(a+1)/2
  • 边界场景当a=0时,每个i仅能匹配j=i一个值,总对数为n,可被上述通用公式完全覆盖。

实现时需要注意两个细节:

  • 当n取到1e6时,计算得到的结果最大可达约5e11,远超32位int的取值上限,因此需要用unsigned long long类型存储变量,避免整数溢出。
  • 代码中单独判断a==0的分支为冗余逻辑,其计算结果可被n>a的通用分支完全覆盖,保留该分支仅为更直观展示边界场景,不影响计算正确性。

优化后代码

#include <iostream>
using namespace std;
int main(){
    unsigned long long n, a, r = 0;
    cin>>n>>a;
    if(a==0){
        r = n;
    }
    if(n<=a){
        r = (n*(n+1))/2;    
    }
    if(n>a){
        r += (n-a)*(a+1) + (a*(a+1))/2;
    }
    cout<<r;
}

内容的提问来源于stack exchange,提问作者ExonegeS

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.11 16:06:04