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 HH1 ≤ 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 NNI IIH HH和R RR。第2 22到第R 1 R1R1行每行两个不同的整数A AA和B BB1 ≤ A 1 \le A1≤A,B ≤ N B \le NB≤N表示奶牛A AA能看到奶牛B BB。输出格式共N NN行第i ii行输出奶牛i ii的最大可能身高。输入输出样例 1输入 19 3 5 5 1 3 5 3 4 3 3 7 9 8输出 15 4 5 3 4 4 5 5 5思路分析初始时假设所有奶牛身高均为最高身高 H。对于每条信息 A 看到 B假设 (AB)意味着区间 (A,B) 内的所有奶牛身高必须严格小于 A 的身高。为了最大化每头奶牛的身高我们只需将区间 (A,B) 内的所有奶牛身高减少 1因为 A本身身高不变中间奶牛减 1 后必定小于 A。使用差分数组维护区间减操作对区间 [A1, B-1] 整体 -1即diff[A1]--、diff[B]。注意去除重复的关系避免多次减同一个区间。最后对差分数组求前缀和得到每头奶牛相对于初始身高 (H) 的减少量输出 (H − 减少量 H - \text{减少量}H−减少量) 即可。代码实现#includebits/stdc.husingnamespacestd;intn,id,h,r,d[10005];// d为差分数组setpairint,intst;// 记录已处理的关系去重intmain(){ios::sync_with_stdio(false);cin.tie(0);// 加速IOcinnidhr;// 读入N, I, H, Rfor(inti0;ir;i){inta,b;cinab;// 读入A, Bif(ab)swap(a,b);// 使abif(st.count({a,b}))continue;// 重复关系跳过st.insert({a,b});if(b-a1){// 区间内至少有一个奶牛d[a1]--;d[b];// 差分区间减1}}intcur0;// 当前减少量for(inti1;in;i){curd[i];// 前缀和得到i的减少量couthcur\n;// 身高 H - 减少量cur为负}return0;}功能分析去重使用setpairint,int确保每条关系只处理一次防止重复减操作。差分维护对区间[a1, b-1]进行整体 (-1)时间复杂度 (O(1))。前缀和还原最后遍历一次累加差分值得到每个位置的减少量输出H 减少量。【完整系列请查看专栏】信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}