算法|题解

计蒜客 – 木桩涂涂看

凝神长老 · 2月14日 · 2020年 · 752次已读

计蒜客 木桩涂涂看

$n$ 个木桩排成一排,从左到右依次编号为 $1, 2, 3…n$。每次给定 $2$ 个整数 $a, b(a \leq b)$,蒜头君便骑上他的电动车从木桩 $a$ 开始到木桩 $b$ 依次给每个木桩涂一次颜色。但是 $n$ 次以后 lele 已经忘记了第 $i$ 个木桩已经涂过几次颜色了,你能帮他算出每个木桩被涂过几次颜色吗?

输入格式
第一行是一个整数 $n(n \leq 100000)$。 接下来的 $n$ 行,每行包括两个整数 $a, b (1 \leq a \leq b \leq n)$。

3
1 1
1 2
1 3

输出格式
$n$ 个整数,第 $i$ 个数代表第 $i$ 个木桩总共被涂色的次数。

3 2 1

这题就是一个裸的差分维护。

#include <bits/stdc++.h>

using namespace std;

int n = 0;
const int MAX_N = 100007;
int dif[MAX_N] = {0};

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        dif[a]++;
        dif[b + 1]--; // 维护差分
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += dif[i];
        printf("%d%c", ans, i == n ? '\n' : ' ');
    }

    return 0;
}
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论