本文写于 2020年02月14日,距今已超过 1 年,距 2020年03月26日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

计蒜客 木桩涂涂看

$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;
}
0 0 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论