最高的牛 Solution

题目传送门：最高的牛

题目

题目描述

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

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

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

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

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

题目大意

将题目简化一下就是：

有 $N$ 头牛，身高最高的是第 $P$ 头牛，身高是 $H$。给定 $M$ 组关系 $a$ 和 $b$，表示 $a,b$ 之间的牛都比他们矮。

还可以用更数学更编程的语言来描述题目，方便此后思考和推理：

有一个 $n$ 个数的数列 $num$，已知 $num_p=h$ 且 $\forall num_i \leq h$ ，给出 $m$ 个区间$[l,r]$，使得 $\forall i \in (l,r)$ 都有 $num_i<num_l$ 且 $num_i<num_r$ ，求最大的 $num$

输入格式

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

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

输出格式

一共输出 $N$ 行数据，每行输出一个整数。

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

数据范围

$1 \leq N \leq 5000,$

$1 \leq H \leq 1000000,$

$1 \leq A,B \leq 10000$ 且 $A \neq B,$

$0 \leq M \leq 10000$

注意：本题中给出的关系可能重复

测试样例

输入样例：

9 3 5 5
1 3
5 3
4 3
3 7
9 8

输出样例：

5
4
5
3
4
4
5
5
5

解题过程

编程是在于数学的基础之上的。在许多编程题都会出现数学相关的知识，所以数学是每个 $\rm OIer$ 的基本技能。而这道题会用到了区间的表示，所以大家要适当的了解一下。

集合：集合

区间：区间

当熟悉了集合和区间之后就可以开始做这道题了。

不管是在考试中还是日常做题的过程中，手算一遍给的样例是必不可少的，尤其是这种题。在手算样例的过程中，我们不仅会对题目有更深的理解，还可能想到解题的思路。第二步就是自己造一两个样例，可以是随机的，也可以是稍微复杂一点的，或者是特殊一点的。造完样例后就再手算一遍自己造的样例，这与算题目给出的样例是一个目的

先算一下题目给出的样例：

9 3 5 5
1 3
5 3
4 3
3 7
9 8

首先牛群的身高我们都是未知的，除了第 $3$ 头牛，像这样的我们肯定需要开一个数组来记录每头牛的最大可能身高，数组命名为 $num$。

这是输入数据后的初始状态：

当输入 “$1,3$” 时，说明第 $1$ 头牛和第 $3$ 头牛中间的牛的身高不能超过第 $1$ 头牛和第 $3$ 头牛。第 $3$ 头牛有确定身高 $5$，而第 $1$ 头牛没有确定身高。因为这时的 $num_1$ 还没有数，就说明第 $1$ 头牛的身高暂时还没有限制，所以目前 $num_1$ 就等于最大的身高 $3$。而 $(1,3)$ 中的数，也就是 $2$ 的身高不能超过 $num_1$ 和 $num_3$ ，所以 $num_2$ 的限制就是 $num[2]<num[1]$ && $num[2]<num[3]$ ，那么 $num_2$ 的最大值就是$\rm min(num_1,num_3)-1=5-1=4$ ，取最小值时因为他要同时小于 $1$ 和 $3$ ，也就是小于 $1$ 和 $3$ 的最小值，而又要 $2$ 尽可能的大，那么最大就是最小值$-1$。

当输入 “$5,3$” 时，同上可以求得$num_4$ 的最大值就是$\rm min(num_3,num_4)-1=5-1=4$ 。

当输入”$4,3$” 时，$3$ 和 $4$ 本来就是挨着的，所以不动：

当输入”$3,7$” 时，$4,5,6$ 都是比 $3$ 和 $7$ 矮的。因为 $7$ 暂时还没有数(就说明 $7$ 的身高还没有被限制)，所以先给 $7$ 赋上一个最大值 $5$ 。然后$3$ 到 $7$ 之内的所有数都不能大于等于 $3$ 和 $7$ ，所以给 $4,5,6$ 赋上 $\rm min(num_3,num_7)-1=4$ 。

最后一个输入 “$9,8$”，因为 $8$ 和$9$ 也是挨着的，所以都赋上个最大值 $5$ 就可以了。

但实际算完会发现与样例输出不一样，是给的样例错了吗（先怀疑样例，再怀疑自己），当然不是的。那么这个时候该怎么办呢？因为先前我们是手算的结果，所以错误只可能错误在输入中，当然不是说样例的输入有问题，而是输入顺序问题。

看一下样例给出的：

1 3
5 3
4 3
3 7
9 8

明显是毫无顺序的，那么接下来我们就该尝试怎样改变顺序可以做对这道题。

那我怎么知道是什么顺序，是左端点从大到小，还是从小到大？是右端点从大到小，还是从小到大？

首先可以用笨办法：试！反正就四种情况：左端点从大到小，右端点从小到大；左端点从大到小，右端点从大到小；左端点从小到大，右端点从大到小；左端点从小到大，右端点从小到大。但这里会出现一种情况，就是有两个或三个排序方法算出来是一样的，那到底应该选哪种呢？所以就只能用到下面的办法了。

我们可以尝试去分析一下怎么个排序法：
首先我们是要统一每组输入中 $a$ 和 $b$ 的大小关系，这里设成 $a>b$，输入就变成了：

1 3
3 5
3 4
3 7
8 9

这里的左端点是从小到大排序的，这个可以根据实际的题意和解题的方法来知道。当左端点相同时按右端点是从大到小排序，也就是左端点相同时按左端点的距离大小排序，距离大的在前，距离小的在后。因为距离越大，所覆盖的数就越多，当从大的右端点转到小的右端点时，有的右端点可能已经赋上值了，且这个值比左端点小，那么左右端点之间的数也会比不排序的时候小。

那么”按左端点从小到大，在左端点相同时按右端点从大到小”的排序方式排序后就是：

1 3
3 7
3 5
3 4
8 9

这样算出来的结果就是对的。

如果大家没有理解为什么这么排序的话，大家可以自己按照上述排序方式模拟一边就知道了。

$AC$ 代码

以下代码的时间复杂度为$\Theta(n+nlogn+nm)$，在这个数据范围下这个时间复杂度是很高的，但使用 $printf$ 和 $scanf$ 后依然能过。如果在考场上要求稳的话，可以用线段树或树状数组等数据结构来优化区间修改的操作（也可以使用一些卡常技巧）。

#include<bits/stdc++.h>

using namespace std;

int n,p,h,m; //有n头牛,给m组关系,最高的一头是p,高度是h
int num[5010]; //记录每一头牛可能的最大身高
struct cow{ //结构体
    int a,b; //表示a和b可以互相看到
}c[10010]; //m组

bool cmp(cow x,cow y){
    if(x.a==y.a) return x.b>y.b; //如果左端点相同,区间长度大的在前(也就是右端点大的在前)
    else return x.a<y.a; //否则按左端点从小到大排序
}

int main(){

    //将num数组初始化为-1,也可以初始化为不可能出现在num中的任何数(-1,0,p+1...),方便后续计算
    memset(num,-1,sizeof num);

    scanf("%d%d%d%d",&n,&p,&h,&m); //输入
    num[p]=h; //第p头牛最高,高度为h
    for(int i=1;i<=m;i++){ //输入m组关系
        scanf("%d%d",&c[i].a,&c[i].b); //第c[i].a头牛和第c[i].b头牛可以互相看见,可以理解为区间[c[i].a,c[i].b]
        if(c[i].a>c[i].b) swap(c[i].a,c[i].b); //始终保持是顺序是位置靠前的那头牛能看见位置靠后的那头牛,也就是左端点始终小于和右端点
    }

    sort(c+1,c+1+m,cmp); //排一下序,按第一头牛从小到大排,也就是让区间左端点从小到大排

    for(int j=1;j<=m;j++){ //枚举m组关系
        if(num[c[j].a]!=-1&&num[c[j].b]!=-1){ //如果区间两端都有数
            // a能看到b当且仅当区间(a,b)中的所有数小于a且小于b,可得区间(a,b)小于min(a,b)
            // 所以区间(a,b)中最大的数只可能是min(a,b)-1
            int tmp=min(num[c[j].a],num[c[j].b]);
            for(int i=c[j].a+1;i<c[j].b;i++){
                num[i]=tmp-1;
            }
        }else if(num[c[j].a]==-1&&num[c[j].b]==-1){ //如果区间两端没有数
            num[c[j].a]=num[c[j].b]=h; //那么说明区间两端暂时还没有限制,所以都设为最大值h,这也就是为什么要按左端点从从小到大排序的原因
            // 同上
            int tmp=min(num[c[j].a],num[c[j].b]);
            for(int i=c[j].a+1;i<c[j].b;i++){
                num[i]=tmp-1;
            }
        }else{ //如果一端有数一端没数
            //哪端没有数就把哪端设为最大值h,因为没有数的那端还没有限制(同上)
            if(num[c[j].a]!=-1){
                num[c[j].b]=h;
            }else{
                num[c[j].a]=h;
            }
            // 同上
            int tmp=min(num[c[j].a],num[c[j].b]);
            for(int i=c[j].a+1;i<c[j].b;i++){
                num[i]=tmp-1;
            }
        }
    }

    for(int i=1;i<=n;i++){
        if(num[i]==-1) num[i]=h; //如果当前的值还是-1,那么说明当前没有被限制,设为最大值h
        printf("%d\n",num[i]); //输出
    }
    return 0;
}

蒟蒻第一次写题解，如有错误，还请各位神犇指出！
写题解不易，给个免费的赞吧！