HackerRank Array Manipulation (差分数组)

Description

Devendra 在 9 号云上看到了他的教练朝他微笑。 每次教授选出 Devendra 单独问他一个问题,Devendra 朦胧的头脑里全是他的教练和她的微笑,以至于他无法专注于其他事情。帮助他解决这个问题:

给你一个长度为 N 的列表,列表的初始值全是 0。对此列表,你要进行 M 次查询,输出列表最终 N 个值的最大值。对每次查询,给你的是 3 个整数—— a, b 和 k,你要对列表中从位置 a 到位置 b 范围内的(包含 a 和 b )的全部元素加上 k。

 

Input Format

第一行包含两个整数 N 和 M

接下来 M 行,每行包含 3 个整数 a, b 和 k

列表中的数位置编号为从 1 到 N

 

Output Format

单独的一行包含最终列表里的最大值

 

Constraints

$3 <= N <= 10^7$

$1 <= M <= 2 \times 10^5$

$1 <= a <= b <= N$

$0 <= k <= 10^9$

 

Sample Input

5 3
1 2 100
2 5 100
3 4 100

 

Sample Output

200

 

思路

这是一类对区间操作先更新后查询的题目,对此,我们可以采用差分数组很方便的完成要求,时间复杂度 $O(n)$。

当然线段树之类的数据结构也是可行的,缺点就是代码太长,敲起来麻烦。

 

AC 代码

#include <bits/stdc++.h>
#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 2e7 + 10;

LL cnt[maxn];
int main() {
#ifdef LOCAL_IM0QIANQIAN
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    IO;
#endif // LOCAL_IM0QIANQIAN

    LL n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        LL a, b, k;
        cin >> a >> b >> k;
        cnt[a - 1] += k;
        cnt[b] -= k;
    }
    LL ans = 0;
    for (int i = 1; i < n; i++) {
        cnt[i] += cnt[i - 1];
        ans = max(ans, cnt[i]);
    }
    cout << ans << endl;
    return 0;
}

  • 2 只已被捕捉
    • 援军 Chrome | 68.0.3440.106 Windows 10

      emmmmm 不明觉厉 千千是大学霸

      • 千千 Chrome | 68.0.3440.106 Linux

        QAQ 突然想做一道题然后找了一个简单的做完发个题解充充数!