---
title: "最高的牛"
created: 2025-11-28
tags:
  - 算法
---

# 最高的牛

## 题目 [最高的牛](https://www.acwing.com/problem/content/description/103/)

![[image-2b4ab9c7.png]]

## 思路分析

![[image-4079df39.png]]

对于每组ab关系其实就是让ab间的数都减去1

所以这点可以使用差分去写

与模板不一样的地方在于 这里是a+1的地方减去1 然后在b那里补回来1

也就是B[a+1]-=1,B[b]+=1; 这样构造回前缀和就能达到ab间所有数减去1的效果

（其实一样的 因为是a+1的到b-1的这一段减去1 也就是：B[a+1]-=1B[b-1+1]+=1）

然后就在于怎么处理这些关系了

它们一定是嵌套或者并列的关系

![[image-3afa9420.png]]

不存在交叉的关系

又因为我们要进行--操作 如果存在重复的ab 那某一段就减去了2次 这是不应该的

所以要进行去重

然后最好这些关系又是a小b大 且一条一条是排好序的

![[image-42bbd1fa.png]]

别左一段右一段的凹 如果是排好序的 那就是有层次的凹

（虽然对程序来说没什么影响 但是对逻辑来看 会清晰很多）

也就是说 我们要对这些关系进行三个操作

先调整成a小b大的形式

然后又要进行排序 还要去重

调成a小b大可以使用swap

排序且去重的话 又是二元组

可以想到用set

它不允许重复的元素 所以可以放心直接把所有处理过的ab insert进行即可

然后因为底层是排序树 会对所有数据进行排序

这完美符合我们的需求

先把所有关系存放进set中 再遍历取出来进行操作即可

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N=10010;
int height[N];
int n,p,h,m;

int main()
{
    cin >> n >> p >> h >> m;
    height[1] = h;
    set<PII> rela;

    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        if(a > b)
            swap(a, b);
        rela.insert({a, b});
    }

    for(auto it = rela.begin(); it != rela.end(); it++)
        height[it->first + 1]--, height[it->second]++;

    for(int i = 1; i <= n; i++)
    {
        height[i] += height[i - 1];
        cout << height[i] << endl;
    }

    return 0;
}
```

## 同类题型

## 视频讲解


---
⬅️ [[2-Learning/02-算法/03-刷题理模型/前缀和与差分相关模型/差分/救生员|救生员]] 🏠 [[00-刷题理模型]] ➡️ [[棋盘|棋盘]]