P8446 虹色的北斗七星题目背景【题目背景与题意无关可以直接阅读题目描述】本题目背景部分改编自真实案例宇佐见莲子是外界的一名大学生在京都的一所大学中专攻超统一物理学最近在做弦论方面的研究。莲子与梅莉一同经营着名为秘封俱乐部的社团。进行着在科学世纪探寻遍布四处的结界的活动。这个月梅莉和莲子又商量着去进行新一轮的探索与发现与贴贴但是在两人手牵手出门的时候甜腻腻的气氛却被一通电话打破。莲子因为经常外出探险同时与梅莉增进感情交流所以作业一拖再拖。她的物理学教授忍无可忍毕竟莲子可是拖了一个学期的物理作业一个字都没有动呢规定她必须在9\sqrt99天之内交上一篇学习报告然后才同意给她的“课外实践活动”报备。这可就没有办法了呢笑莲子只好先努力在 deadline 之前糊弄完她的学习报告然后才能执行她们观赏夜空的计划。题目描述由于前两天都被莲子用来进行活动的筹备工作了所以现在她只有几分钟的时间糊弄作业。尽管这样不太好但是她别无选择只能从之前的课堂笔记中摘取一段内容。莲子的课堂笔记共有nnn章每章分别记着不同的内容。她可以选择其中任意连续的一段[l,r][l,r][l,r]表示选取了第lll章到第rrr章作为最终的成果。每一章的内容各不相同老师对每章内容有一个评价分aia_iai。因为学习报告要体现出学生的进步所以老师的满意度将会加上其中最差min{ai}\min\{a_i\}min{ai}和最好章节max{ai}\max\{a_i\}max{ai}的评价分差距。因为直接把冗长的课堂笔记作为报告提交显得太敷衍所以每存在一章内容老师的满意度就会−1-1−1。形式化地来说如果莲子提交了[l,r][l,r][l,r]这一段区间的笔记老师的满意度将会是max{al,al1,⋯ ,ar}−min{al,al1,⋯ ,ar}−(r−l1)\max\{a_l,a_{l1},\cdots,a_r\}-\min\{a_l,a_{l1},\cdots,a_r\}-(r-l1)max{al,al1,⋯,ar}−min{al,al1,⋯,ar}−(r−l1)。莲子希望你能帮她找出一种使得老师的满意度最大的方案。因为她非常聪明所以只需要你告诉她这个最大的满意度她就会知道应该怎么做。【形式化题意】你有一个长度为nnn的序列aaa它的一个区间[l,r][l,r][l,r]的价值是max{al,al1,⋯ ,ar}−min{al,al1,⋯ ,ar}−rl−1\max\{a_l,a_{l1},\cdots,a_r\}-\min\{a_l,a_{l1},\cdots,a_r\}-rl-1max{al,al1,⋯,ar}−min{al,al1,⋯,ar}−rl−1。求这个序列价值最大的子区间并输出这个价值。输入格式第一行输入一个正整数nnn表示笔记的章节数。第二行输入评价分序列aaa以空格隔开每一个元素。输出格式输出这个评价分序列中老师满意度最大的子区间的满意度。输入输出样例 #1输入 #16 5 2 4 2 8 8输出 #14说明/提示【样例解释和说明】令l4,r5l4,r5l4,r5则有min{a4,a5}2\min\{a_4,a_5\}2min{a4,a5}2max{a4,a5}8\max\{a_4,a_5\}8max{a4,a5}8贡献值为444。易证这是满意度最大的子区间。【数据范围】对于20%20\%20%的数据n≤5×103n\leq 5\times 10^3n≤5×103。另有20%20\%20%的数据所有的aia_iai都相等。对于100%100\%100%的数据1≤n≤4×1061\le n\le 4\times10^61≤n≤4×1061≤ai≤1091 \leq a_i \leq 10^91≤ai≤109。C实现#includebits/stdc.h#defineN4000005#definelllonglongusingnamespacestd;intn,a[N],b[N],ans-1;inlineintread(){intx0,f1;charchgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){x(x1)(x3)(ch^48);chgetchar();}returnx*f;}intmain(){nread();for(inti1;in;i)a[i]read(),b[i]a[i]-i;for(inti1,mn1e9;in;i){mnmin(b[i],mn);ansmax(ans,b[i]-mn);b[i]a[i]i;}for(inti1,mx-1e9;in;i){mxmax(b[i],mx);ansmax(ans,mx-b[i]);}coutans-1;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3234）用C++实现信奥题 P8446 虹色的北斗七星
P8446 虹色的北斗七星题目背景【题目背景与题意无关可以直接阅读题目描述】本题目背景部分改编自真实案例宇佐见莲子是外界的一名大学生在京都的一所大学中专攻超统一物理学最近在做弦论方面的研究。莲子与梅莉一同经营着名为秘封俱乐部的社团。进行着在科学世纪探寻遍布四处的结界的活动。这个月梅莉和莲子又商量着去进行新一轮的探索与发现与贴贴但是在两人手牵手出门的时候甜腻腻的气氛却被一通电话打破。莲子因为经常外出探险同时与梅莉增进感情交流所以作业一拖再拖。她的物理学教授忍无可忍毕竟莲子可是拖了一个学期的物理作业一个字都没有动呢规定她必须在9\sqrt99天之内交上一篇学习报告然后才同意给她的“课外实践活动”报备。这可就没有办法了呢笑莲子只好先努力在 deadline 之前糊弄完她的学习报告然后才能执行她们观赏夜空的计划。题目描述由于前两天都被莲子用来进行活动的筹备工作了所以现在她只有几分钟的时间糊弄作业。尽管这样不太好但是她别无选择只能从之前的课堂笔记中摘取一段内容。莲子的课堂笔记共有nnn章每章分别记着不同的内容。她可以选择其中任意连续的一段[l,r][l,r][l,r]表示选取了第lll章到第rrr章作为最终的成果。每一章的内容各不相同老师对每章内容有一个评价分aia_iai。因为学习报告要体现出学生的进步所以老师的满意度将会加上其中最差min{ai}\min\{a_i\}min{ai}和最好章节max{ai}\max\{a_i\}max{ai}的评价分差距。因为直接把冗长的课堂笔记作为报告提交显得太敷衍所以每存在一章内容老师的满意度就会−1-1−1。形式化地来说如果莲子提交了[l,r][l,r][l,r]这一段区间的笔记老师的满意度将会是max{al,al1,⋯ ,ar}−min{al,al1,⋯ ,ar}−(r−l1)\max\{a_l,a_{l1},\cdots,a_r\}-\min\{a_l,a_{l1},\cdots,a_r\}-(r-l1)max{al,al1,⋯,ar}−min{al,al1,⋯,ar}−(r−l1)。莲子希望你能帮她找出一种使得老师的满意度最大的方案。因为她非常聪明所以只需要你告诉她这个最大的满意度她就会知道应该怎么做。【形式化题意】你有一个长度为nnn的序列aaa它的一个区间[l,r][l,r][l,r]的价值是max{al,al1,⋯ ,ar}−min{al,al1,⋯ ,ar}−rl−1\max\{a_l,a_{l1},\cdots,a_r\}-\min\{a_l,a_{l1},\cdots,a_r\}-rl-1max{al,al1,⋯,ar}−min{al,al1,⋯,ar}−rl−1。求这个序列价值最大的子区间并输出这个价值。输入格式第一行输入一个正整数nnn表示笔记的章节数。第二行输入评价分序列aaa以空格隔开每一个元素。输出格式输出这个评价分序列中老师满意度最大的子区间的满意度。输入输出样例 #1输入 #16 5 2 4 2 8 8输出 #14说明/提示【样例解释和说明】令l4,r5l4,r5l4,r5则有min{a4,a5}2\min\{a_4,a_5\}2min{a4,a5}2max{a4,a5}8\max\{a_4,a_5\}8max{a4,a5}8贡献值为444。易证这是满意度最大的子区间。【数据范围】对于20%20\%20%的数据n≤5×103n\leq 5\times 10^3n≤5×103。另有20%20\%20%的数据所有的aia_iai都相等。对于100%100\%100%的数据1≤n≤4×1061\le n\le 4\times10^61≤n≤4×1061≤ai≤1091 \leq a_i \leq 10^91≤ai≤109。C实现#includebits/stdc.h#defineN4000005#definelllonglongusingnamespacestd;intn,a[N],b[N],ans-1;inlineintread(){intx0,f1;charchgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){x(x1)(x3)(ch^48);chgetchar();}returnx*f;}intmain(){nread();for(inti1;in;i)a[i]read(),b[i]a[i]-i;for(inti1,mn1e9;in;i){mnmin(b[i],mn);ansmax(ans,b[i]-mn);b[i]a[i]i;}for(inti1,mx-1e9;in;i){mxmax(b[i],mx);ansmax(ans,mx-b[i]);}coutans-1;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
