AcWing 101. 最高的牛

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

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

作者：

秦淮岸灯火阑珊 , 2019-01-20 17:46:58 , 所有人可见 , 阅读 6494

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$

样例

差分+区间处理小操作

这道题目一个核心要点，就是如何处理这些特殊的关系，也就是两头牛互相看见。

其实题目中已经告诉我们如何处理，因为我们发现，题目中要求牛的身高最高，那么既然如此，我们完全可以将每一组关系 $(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 4
3 4

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

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

wh2011 2023-11-04 13:36

判断重复的地方错了

hack 数据：

应输出：

小灰爱吃羊 6个月前

数据出现（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

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

经年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