奶牛身高问题解析

这道题目要求我们根据已知的"奶牛能看到奶牛"的约束条件，计算每头奶牛可能的最大身高。这是一个典型的区间约束问题，可以使用差分数组高效解决。

解题思路

1. 问题分析：

   • 对于每对(A,B)，表示奶牛A能看到奶牛B
   • 这意味着：
     • A和B的身高至少为H（最高奶牛的身高）
     • A和B之间的所有奶牛（A+1到B-1）的身高必须严格小于A和B的身高
   • 我们需要计算每头奶牛的最大可能身高

2. 关键观察：

   • 对于每对(A,B)，A和B之间的奶牛身高必须严格小于A和B
   • 为了最大化每头奶牛的身高，我们应该让A和B之间的奶牛身高尽量高，但仍满足约束
   • 这意味着A和B之间的奶牛身高应比A和B的身高小1

3. 差分数组技巧：

   • 对于每个约束(A,B)，我们需要将区间[A+1,B-1]的所有奶牛身高减1
   • 使用差分数组可以高效地实现区间修改
   • 差分数组d[i]表示原数组c[i]与c[i-1]的差值
   • 修改区间[l,r]时，只需d[l]++和d[r+1]--

代码解析

下面是完整的C++代码，我将对关键部分进行解释：

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
map<pair<int,int>,bool> existed;
int d[10005],c[10005];
int main()
{
    int n,i,h,r;
    cin>>n>>i>>h>>r;
    int a,b;
    while(r--)
    {
        scanf("%d%d",&a,&b);
        if(a>b) swap(a,b);
        if(existed[make_pair(a,b)]) continue;
        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",c[i]+h);
    }
    return 0;
}

算法步骤

1. 输入处理：

   • 读取奶牛数量N、最高奶牛编号I、最高奶牛身高H、约束数量R
   • 对于每个约束(A,B)，确保A<B（如果A>B则交换）

2. 差分数组更新：

   • 使用map记录已经处理过的约束对，避免重复处理
   • 对于每个新约束(A,B)，更新差分数组：
     • d[A+1]--：表示从A+1开始，身高减少1
     • d[B]++：表示到B为止，身高不再减少（恢复原值）

3. 计算每头奶牛的身高：

   • 通过差分数组还原原数组c[i]：c[i] = c[i-1] + d[i]
   • 每头奶牛的最终身高为：c[i] + H
   • 初始时所有奶牛的身高都设为H，然后根据约束进行调整

时间复杂度分析

• 读取输入：O(R)
• 处理约束：O(R log R)，主要是map的查找和插入操作
• 计算身高：O(N)
• 总体时间复杂度：O(R log R + N)，适用于N≤10,000和R≤10,000的规模

空间复杂度分析

• 存储差分数组：O(N)
• 存储约束对：O(R)
• 总体空间复杂度：O(N + R)

算法正确性证明

1. 差分数组的作用：

   • 差分数组d[i]表示原数组c[i]与c[i-1]的差值
   • 修改区间[l,r]时，只需d[l]++和d[r+1]--
   • 这样在还原原数组时，区间[l,r]内的所有元素都会增加1

2. 约束的处理：

   • 对于约束(A,B)，我们需要将区间[A+1,B-1]的所有奶牛身高减1
   • 通过d[A+1]--和d[B]++，我们确保了区间[A+1,B-1]内的所有奶牛身高都比A和B的身高小1
   • 这满足了"奶牛A能看到奶牛B"的约束条件

3. 最大化身高：

   • 我们从最高身高H开始，只在必要时降低某些奶牛的身高
   • 这确保了每头奶牛的身高都是最大可能值

通过这种方式，我们高效地解决了这个区间约束问题，计算出了每头奶牛可能的最大身高。