AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 101. 最高的牛    原题链接    中等

作者: 作者的头像   秦淮岸灯火阑珊 ,  2019-01-20 17:46:58 ,  所有人可见 ,  阅读 6565


31


9

题目描述

有 $N$ 头牛站成一行,被编队为$1、2、3…N$,每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时,两头牛方可看到对方。

现在,我们只知道其中最高的牛是第 $P$ 头,它的身高是 $H$ ,剩余牛的身高未知。

但是,我们还知道这群牛之中存在着 $M$ 对关系,每对关系都指明了某两头牛 $A$ 和 $B$ 可以相互看见。

求每头牛的身高的最大可能值是多少。

输入格式
第一行输入整数$N,P,H,M$,数据用空格隔开。

接下来M行,每行输出两个整数 $A$ 和 $B$ ,代表牛 $A$ 和牛 $B$ 可以相互看见,数据用空格隔开。

输出格式
一共输出 $N$ 行数据,每行输出一个整数。

第 $i$ 行输出的整数代表第 $i$ 头牛可能的最大身高。

数据范围
$1≤N≤10000, 1≤H≤1000000, 1≤A,B≤10000, 0≤M≤10000$

样例

输入样例:
9 3 5 5
1 3
5 3
4 3
3 7
9 8
输出样例:
5
4
5
3
4
4
5
5
5

差分+区间处理小操作

这道题目一个核心要点,就是如何处理这些特殊的关系,也就是两头牛互相看见。
其实题目中已经告诉我们如何处理,因为我们发现,题目中要求牛的身高最高,那么既然如此,我们完全可以将每一组关系$(A,B)$,看作$[A+1,B-1]$这组牛身高只比$A,B$这两头牛矮1.
各位可以画一个图,来更好的理解这道题目。

最高的牛.png

因此我们可以可以利用区间处理小操作,也就是前缀和加差分。设一个数组$D$,$D[i]$为比最高牛矮多少,则$D[P]=0$,那么对于一组关系,我们可以这样操作,D[A+1]–,D[B]++;然后从左到右前缀和,就可以求出矮多少。具体可以看代码实现。
本题数据内部可能重复,要判重,还有$[l,r]$不一定$l<r$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
pair<ll,ll> a[10100];
map<ll,ll> q;
ll n,m,i,j,k,p,h,c[10100],d[10100];
int main()
{
    cin>>n>>p>>h>>m;
    for (i=1;i<=m;i++)
    {
        ll A,B;
        cin>>A>>B;
        if (A>B)
            swap(A,B);
        if (q[A]!=B)
            a[i]=make_pair(A,B),q[A]=B,d[A+1]--,d[B]++;
    }
    for (i=1;i<=n;i++)
        c[i]=c[i-1]+d[i];
    for (i=1;i<=n;i++)
        cout<<c[i]+h<<endl;
}

41 评论


用户头像
eeach   2020-02-26 22:45      3    踩      回复

这里我终于明白了,所谓的数据有重复是指
``` 3 4
3 4

这种,而不是
``` 3    4
     3    5
     3    4

所以q[A]!=B能够去重是这个道理


用户头像
wh2011   2023-11-04 13:36      1    踩      回复

判断重复的地方错了

hack 数据:

7 1 7 4
2 4
2 5
2 4
2 5

应输出:

7
7
5
6
7
7
7

用户头像
小灰爱吃羊   2024-08-21 01:00         踩      回复

数据出现(3,7)和(3,5)的时候
q[3]=7和q[3]=5会重复


用户头像
容淘淘   2023-07-22 14:49         踩      回复

为啥开long long 兄弟们


用户头像
Xiongzx   2023-02-17 08:44         踩      回复

同方法ac代码
rd();是快读

#include <bits/stdc++.h>
#define fi first
#define se second
#define prf printf
#define PII pair<int, int>

using namespace std;

template <typename T> inline void rd(T &x){
    x = 0; bool f = true; char ch = getchar();
    while(ch < '0' || ch > '9'){ f = ch == '-' ? false : true; ch = getchar();}
    while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
    if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}
/*****************************/
const int N = 5010;
PII ran;
map<PII, bool> m;
int n, p, h, T;
int dif[N];

int main(){
    rd(n, p, h, T);
    dif[1] = h;
    while(T--){
        int l, r; rd(l, r);
        if(l > r) swap(l, r);
        auto temp = make_pair(l, r);
        if(!m[temp]){
            m[temp] = true;
            dif[temp.fi + 1]--;
            dif[temp.se]++;
        }
    }
    for(int i = 1; i <= n; i++) dif[i] += dif[i - 1];
    for(int i = 1; i <= n; i++) prf("%d\n", dif[i]);
    return 0;
}


用户头像
zivo   2023-01-03 17:06         踩      回复

#### ####

用户头像
zivo   2023-01-03 17:07         踩      回复

#### ####


用户头像
cisdes   2022-01-20 20:12         踩      回复

AC不了


用户头像
code_dance_ssp   2022-01-06 17:02         踩      回复

代码ac不了,应该是判重有问题


用户头像
ZCPUZZLE   2021-07-26 16:28         踩      回复

a[i]=make_pair(A,B),这一句有什么用

用户头像
冷_6   2021-08-07 17:34      1    踩      回复

题目的测试数据好像有问题吧?@_@


用户头像
经年reminis   2019-11-15 20:26         踩      回复

have some problems
first map cant judge chong fu shu ju second the heightest cow cant modify it value
use set[HTML_REMOVED] >st
!count ke yi panduan shibushifangwenguo

用户头像
秦淮岸灯火阑珊   2019-11-15 20:47         踩      回复

咋了

用户头像
jyeric   2020-01-19 18:16    回复了 秦淮岸灯火阑珊 的评论         踩      回复

他的意思是指 碰到相同的$a$,但是$b$不同的情况 map会炸


用户头像
ganixdd   2019-08-13 17:35         踩      回复

q[A]!=B 那里不对呀。。

附个数据
7 1 7 4
2 4
2 5
2 4
2 5

用户头像
秦淮岸灯火阑珊   2019-08-13 18:06         踩      回复

那么您这个数据,应该输出什么呢?

用户头像
ganixdd   2019-08-13 18:31    回复了 秦淮岸灯火阑珊 的评论         踩      回复

7
7
5
6
7
7

用户头像
秦淮岸灯火阑珊   2019-08-13 18:41    回复了 ganixdd 的评论         踩      回复

您稍等啊,我待会晚上有Acwing直播,现在正在备课。

用户头像
秦淮岸灯火阑珊   2019-08-13 18:41    回复了 ganixdd 的评论         踩      回复

您稍等啊,我待会晚上有Acwing直播,现在正在备课。

用户头像
eeach   2020-02-26 22:23         踩      回复

我也感觉不太对,这里到底怎么回事?

用户头像
zzx1543   2020-04-30 22:17    回复了 ganixdd 的评论         踩      回复

少了个7
7
7
5
6
7
7
7

用户头像
code_dance_ssp   2022-01-06 17:10         踩      回复

这个判重的确不行,得用set存储pair(A,B)来判断。


用户头像
Andrew82   2019-08-12 18:10         踩      回复

how 鬼畜 the STL is!

用户头像
秦淮岸灯火阑珊   2019-08-12 18:13         踩      回复

emm

用户头像
Andrew82   2019-08-12 18:20    回复了 秦淮岸灯火阑珊 的评论         踩      回复

为什么不用pair在本地dev上可以AC,但是评测WA
用了pair在本地就WA,评测AC...........

用户头像
秦淮岸灯火阑珊   2019-08-12 19:47    回复了 Andrew82 的评论         踩      回复

不会吧。您是不是编译器版本有点问题呢?
还有您指的AC,是样例通过,还是所有数据都通过呢?

用户头像
Andrew82   2019-08-12 19:55    回复了 秦淮岸灯火阑珊 的评论         踩      回复

哦好像是编译器出了点问题,谢谢回复 @~@

用户头像
秦淮岸灯火阑珊   2019-08-13 06:27    回复了 Andrew82 的评论         踩      回复

您客气了,应该的。


用户头像
Mintind   2019-07-03 06:36         踩      回复

为什么q[A]!=B就说明(A,B)没有出现过 q[A]不是会被覆盖吗

用户头像
秦淮岸灯火阑珊   2019-07-18 19:49         踩      回复

一头牛对应一头牛.所有牛的身高不一样.

用户头像
Mintind   2019-07-20 21:25    回复了 秦淮岸灯火阑珊 的评论         踩      回复

啊对哦 谢谢

用户头像
eeach   2020-02-26 22:22    回复了 Mintind 的评论         踩      回复

为啥我还是没看懂


用户头像
robot_1   2019-06-02 14:14         踩      回复

a[i]=make_pair(A,B)是什么意思呢

用户头像
song666   2019-07-18 16:53         踩      回复

就是一个pair类型,把make_pair里的数分别“移植”到这个pair类型里


用户头像
以依为终   2019-05-12 13:21         踩      回复

我懂啦!题目有个前提,或者说隐含条件,就是对于所有AB区间,他们除了端点之外不可能有交集,所以可以这样直接区间同时减1


用户头像
Pashion   2019-03-30 10:38         踩      回复

讲解有地方错了 是D[A+1]–- 而不是D[A-1]–-

用户头像
秦淮岸灯火阑珊   2019-03-30 16:22         踩      回复

万分感谢!打错了.


用户头像
Nicoppa   2019-03-08 13:45         踩      回复

这里的a数组是用来做什么的。。。

用户头像
秦淮岸灯火阑珊   2019-03-08 19:13         踩      回复

负责记录

用户头像
Nicoppa   2019-03-12 12:57    回复了 秦淮岸灯火阑珊 的评论         踩      回复

但是好像不要这个也没什么关系..

用户头像
秦淮岸灯火阑珊   2019-03-12 19:21    回复了 Nicoppa 的评论         踩      回复

也是,你可以自行忽略这个多余的东西


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息