P8446 虹色的北斗七星

题目背景

【题目背景与题意无关，可以直接阅读题目描述】

（本题目背景部分改编自真实案例）

宇佐见莲子是外界的一名大学生，在京都的一所大学中专攻超统一物理学，最近在做弦论方面的研究。

莲子与梅莉一同经营着名为秘封俱乐部的社团。进行着在科学世纪探寻遍布四处的结界的活动。

这个月梅莉和莲子又商量着去进行新一轮的探索与发现与贴贴，但是在两人手牵手出门的时候甜腻腻的气氛却被一通电话打破。

莲子因为经常外出探险，同时与梅莉增进感情交流，所以作业一拖再拖。她的物理学教授忍无可忍（毕竟莲子可是拖了一个学期的物理作业一个字都没有动呢），规定她必须在 $\sqrt{9}$ 天之内交上一篇学习报告，然后才同意给她的“课外实践活动”报备。

这可就没有办法了呢（笑），莲子只好先努力在 deadline 之前糊弄完她的学习报告，然后才能执行她们观赏夜空的计划。

题目描述

由于前两天都被莲子用来进行活动的筹备工作了，所以现在她只有几分钟的时间糊弄作业。尽管这样不太好，但是她别无选择，只能从之前的课堂笔记中摘取一段内容。

莲子的课堂笔记共有 $n$ 章，每章分别记着不同的内容。她可以选择其中任意连续的一段 $[l,r]$（表示选取了第 $l$ 章到第 $r$ 章）作为最终的成果。

每一章的内容各不相同，老师对每章内容有一个评价分 $a_i$。因为学习报告要体现出学生的进步，所以老师的满意度将会加上其中最差（min⁡{ai}\min\{a_i\}min{ai​}）和最好章节（max⁡{ai}\max\{a_i\}max{ai​}）的评价分差距。因为直接把冗长的课堂笔记作为报告提交显得太敷衍，所以每存在一章内容，老师的满意度就会 $-1$。

形式化地来说，如果莲子提交了 $[l,r]$ 这一段区间的笔记，老师的满意度将会是 max⁡{al,al+1,⋯ ,ar}−min⁡{al,al+1,⋯ ,ar}−(r−l+1)\max\{a_l,a_{l+1},\cdots,a_r\}-\min\{a_l,a_{l+1},\cdots,a_r\}-(r-l+1)max{al​,al+1​,⋯,ar​}−min{al​,al+1​,⋯,ar​}−(r−l+1)。

莲子希望你能帮她找出一种使得老师的满意度最大的方案。因为她非常聪明，所以只需要你告诉她这个最大的满意度，她就会知道应该怎么做。

【形式化题意】

你有一个长度为 $n$ 的序列 $a$，它的一个区间 $[l,r]$ 的价值是 max⁡{al,al+1,⋯ ,ar}−min⁡{al,al+1,⋯ ,ar}−r+l−1\max\{a_l,a_{l+1},\cdots,a_r\}-\min\{a_l,a_{l+1},\cdots,a_r\}-r+l-1max{al​,al+1​,⋯,ar​}−min{al​,al+1​,⋯,ar​}−r+l−1。求这个序列价值最大的子区间并输出这个价值。

输入格式

第一行输入一个正整数 $n$，表示笔记的章节数。

第二行输入评价分序列 $a$，以空格隔开每一个元素。

输出格式

输出这个评价分序列中，老师满意度最大的子区间的满意度。

输入输出样例 #1

输入 #1

6
5 2 4 2 8 8

输出 #1

4

说明/提示

【样例解释和说明】

令 $l=4,r=5$，则有 min⁡{a4,a5}=2\min\{a_4,a_5\}=2min{a4​,a5​}=2，max⁡{a4,a5}=8\max\{a_4,a_5\}=8max{a4​,a5​}=8，贡献值为 $4$。易证这是满意度最大的子区间。

【数据范围】

• 对于 $20\%$ 的数据，$n\le 5\times 10^3$。
• 另有 $20\%$ 的数据，所有的 $a_i$ 都相等。
• 对于 $100\%$ 的数据，$1\le n\le 4\times 10^6$，$1\le a_i\le 10^9$。

C++实现

#include<bits/stdc++.h>
#define N 4000005
#define ll long long
using namespace std;
int n,a[N],b[N],ans=-1;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main(){
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),b[i]=a[i]-i;
	for(int i=1,mn=1e9;i<=n;i++){
		mn=min(b[i],mn);
		ans=max(ans,b[i]-mn);
		b[i]=a[i]+i;
	}
	for(int i=1,mx=-1e9;i<=n;i++){
		mx=max(b[i],mx);
		ans=max(ans,mx-b[i]);
	}
	cout<<ans-1;
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容