最高的牛Tallest Cow(前缀和)- POJ 3263

Description

FJ's N (1 ≤ N ≤ 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (which is a bit of secret). You are told only the height H (1 ≤ H ≤ 1,000,000) of the tallest cow along with the index I of that cow.

FJ has made a list of R (0 ≤ R ≤ 10,000) lines of the form "cow 17 sees cow 34". This means that cow 34 is at least as tall as cow 17, and that every cow between 17 and 34 has a height that is strictly smaller than that of cow 17.

For each cow from 1..N, determine its maximum possible height, such that all of the information given is still correct. It is guaranteed that it is possible to satisfy all the constraints.

Input

Line 1: Four space-separated integers: N, I, H and R

Lines 2..R+1: Two distinct space-separated integers A and B (1 ≤ A, B ≤ N), indicating that cow A can see cow B.

Output

Lines 1..N: Line i contains the maximum possible height of cow i.

Sample Input

9 3 5 5

1 3

5 3

4 3

3 7

9 8

Sample Output

5

4

5

3

4

4

5

5

5

概译:N头牛排成一排,只知道最高的牛的下标I和它的高度H,然后给出R行,每行的A、B表示A可以看到B。而A可以看到B的定义为:B至少和A等高且A到B之间的牛全都严格比A矮。输出各个牛最大可能身高。

因为数据一定合法所以可以朴素地先都假设等于最高,然后每次输入A和B都把A+1~B-1之间的牛的高度都减一。但复杂度O(NR)较大,可以用前缀和的思想优化,即:把对一个区间的操作转化为左右两个端点上的操作。此题可以开一个额外的数组d,每输入A、B后,在d上的A+1下标处“--”意味着从此处开始要变矮,B下标处“++”意味着在此处结束,而d数组直接负责的是c数组,c数组代表的是第i头牛和第I头牛的身高差距,即c[I]一定等于0。

详见代码:G++

#include<iostream>
#include<cstdio>
#include<map>
#include<utility>
using namespace std;

const int maxn = 10005;
int n, I, h, r;
int c[maxn], d[maxn];
map<pair<int, int>, bool>existed;

int main()
{
    cin >> n >> I >> h >> r;
    for (int i = 0; i < r; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a > b)  swap(a, b);
        if (existed[make_pair(a, b)])   continue;
        //map判断一下是否曾经操作过了
        d[a + 1]--, d[b]++;
        existed[make_pair(a, b)] = true;
    }

    for (int i = 1; i <= n; i++)
    {
        c[i] = c[i - 1] + d[i];
        printf("%d\n", h + c[i]);
    }
    return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-04-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏斑斓

当函数成为一等公民时,设计模式的变化

GOF提出的设计模式,其本质思想是封装变化。故而,创建型模式封装的是对象创建的变化,结构型模式封装的是对象之间的协作与组合结构,行为型模式则封装了对象行为的变化...

3105
来自专栏程序人生

谈谈面向对象编程

最近写了些和函数式编程的文章,有读者和我讨论函数式编程和面向对象编程的优劣。二者都是很好的编程思想,都在着力解决代码重用的问题,也彼此吸收对方的优点,所以大可不...

42411
来自专栏北京马哥教育

Python 工匠:善用变量来改善代码质量

1598
来自专栏Petrichor的专栏

什么是:语法糖、语法盐、语法糖精

4035
来自专栏阿凯的Excel

Python读书笔记23(浅谈为什么要用类)

题外话:好几个朋友和我提出最好能写一个Python入门的合集版,我会尽快将基础知识分享完,然后重新整理一下过去分享的所有材料。 如果只是想学P...

3596
来自专栏静默虚空的博客

查找三 哈希表的查找

要点 哈希表和哈希函数 在记录的存储位置和它的关键字之间是建立一个确定的对应关系(映射函数),使每个关键字和一个存储位置能唯一对应。这个映射函数称为哈希函数,根...

3755
来自专栏Java帮帮-微信公众号-技术文章全总结

第八天 自定义类型方法集合混合使用【悟空教程】

2028
来自专栏程序你好

Java和c++构造函数的区别是什么?

如果你是一个c++程序员,现在正在学习Java,你会发现这两种流行的面向对象编程语言有很多相似之处。这两种语言都支持抽象、封装、类、对象和其他OOP概念。但是,...

1074
来自专栏我杨某人的青春满是悔恨

《编程的智慧(初稿)》读后感

王垠更新了文章,加入了Optional跟Union比较的内容,所以我也来更新一下。垠神认为Optional并没有什么卵用,Java8的Optional我不是很了...

1052
来自专栏Crossin的编程教室

【Python 第21课】 函数的参数

今天发现了一个iPad上的游戏,叫Cargo-Bot。这个游戏需要你用指令控制一个机械臂去搬箱子。游戏里蕴含了很多编程的思想,包括循环、函数调用、条件判断、寄...

3319

扫码关注云+社区

领取腾讯云代金券