csp信奥赛C++高频考点专项训练之前缀和差分 --【一维差分】：[USACO07JAN] Tallest Cow S

csp信奥赛C++高频考点专项训练之前缀和&差分 --【一维差分】：[USACO07JAN] Tallest Cow S

题目描述

FJ 的N NN头奶牛（1 ≤ N ≤ 10 , 000 1 \le N \le 10,0001≤N≤10,000）按编号1 11到N NN排成一行。每头奶牛有一个正整数表示的身高（这是个秘密）。现在你只知道最高奶牛的身高H HH（1 ≤ H ≤ 1 , 000 , 000 1 \le H \le 1,000,0001≤H≤1,000,000），以及它的编号I II。

FJ 提供了R RR条信息（0 ≤ R ≤ 10 , 000 0 \le R \le 10,0000≤R≤10,000），每条信息形如“奶牛 17 能看到奶牛 34”。这意味着奶牛 34 的身高不小于奶牛 17 的身高，并且编号在 17 和 34 之间的所有奶牛，其身高都严格小于奶牛 17 的身高。

现在请你计算出对于每一头奶牛（编号从1 11到N NN），在所有给定信息都成立的前提下，它可能具有的最大身高。

题目保证一定存在满足条件的解。

输入格式

第1 11行：四个用空格分隔的整数：N NN，I II，H HH和R RR。

第2 22到第R + 1 R+1R+1行：每行两个不同的整数A AA和B BB（1 ≤ A 1 \le A1≤A,B ≤ N B \le NB≤N），表示奶牛A AA能看到奶牛B BB。

输出格式

共N NN行，第i ii行输出奶牛i ii的最大可能身高。

输入输出样例 1

输入 1

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

输出 1

5 4 5 3 4 4 5 5 5

思路分析

• 初始时，假设所有奶牛身高均为最高身高 H。
• 对于每条信息 A 看到 B（假设 (A<B)），意味着区间 (A,B) 内的所有奶牛身高必须严格小于 A 的身高。为了最大化每头奶牛的身高，我们只需将区间 (A,B) 内的所有奶牛身高减少 1（因为 A本身身高不变，中间奶牛减 1 后必定小于 A）。
• 使用差分数组维护区间减操作：对区间 [A+1, B-1] 整体 -1，即diff[A+1]--、diff[B]++。
• 注意去除重复的关系，避免多次减同一个区间。
• 最后对差分数组求前缀和，得到每头奶牛相对于初始身高 (H) 的减少量，输出 (H − 减少量 H - \text{减少量}H−减少量) 即可。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,id,h,r,d[10005];// d为差分数组set<pair<int,int>>st;// 记录已处理的关系，去重intmain(){ios::sync_with_stdio(false);cin.tie(0);// 加速IOcin>>n>>id>>h>>r;// 读入N, I, H, Rfor(inti=0;i<r;++i){inta,b;cin>>a>>b;// 读入A, Bif(a>b)swap(a,b);// 使a<bif(st.count({a,b}))continue;// 重复关系跳过st.insert({a,b});if(b-a>1){// 区间内至少有一个奶牛d[a+1]--;d[b]++;// 差分区间减1}}intcur=0;// 当前减少量for(inti=1;i<=n;++i){cur+=d[i];// 前缀和得到i的减少量cout<<h+cur<<'\n';// 身高 = H - 减少量（cur为负）}return0;}

功能分析

• 去重：使用set<pair<int,int>>确保每条关系只处理一次，防止重复减操作。
• 差分维护：对区间[a+1, b-1]进行整体 (-1)，时间复杂度 (O(1))。
• 前缀和还原：最后遍历一次，累加差分值得到每个位置的减少量，输出H + 减少量。

【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}