全部评论 1

  • 1、枚举算法
    1、枚举所有情况
    2、判断每种情况是否符合条件

    2、贪心算法
    1、贪
    排序

    bool cmp(int x,int y){
        return x>y; // > 从大到小; < 从小到大 
    }
    
    sort(a+1,a+n+1); // 从小到大
    sort(a+1,a+n+1,greater<int>()); // 从大到小
    sort(a+1,a+n+1,cmp); // 从大到小
    

    3、前缀和
    定义: s[i]: 原数组 a 的前 i 个数(1 ~ i)的和

    预处理: s[i] = s[i-1] + a[i]
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    
    应用: 求区间 [L,R] 的区间和 sum(L,R)
        sum(L,R) = s[R] - s[L-1];
    
    用在有 多次 查询 区间和 的问题 O(1)
    

    4、差分
    定义: d[i]: 原数组 a 的相邻两项元素的差值

    预处理: d[i] = a[i] - a[i-1];
    for(int i=1;i<=n;i++) d[i]=a[i]-a[i-1];
    
    应用: 对原数组 a 区间 [L,R] 每个数加上 c
    
        d[L]+=c;
        d[R+1]-=c;
    
        直接对原数组 a 进行修改, 一次修改 时间复杂度 O(n);
        
        间接对差分数组 d 进行修改, 一次修改 时间复杂度 O(1),
        再通过对差分数组求前缀和得到修改后的原数组了 O(n);
    
    用在有 多次 区间修改 的问题
    

    5、原 前 差的转换

    2小时前 来自 浙江

    0

热门讨论