Description

Input

第一行一个整数 n 表示数列长度，第二行 n 个整数 a1 ~an 。

Output

输出一行一个整数表示答案 。

Sample Input

5
50 30 40 10 20

Sample Output

2

Data Constraint

Subtask 1 (24pts)：n<=20。
Subtask 2 (16pts)：n<=100。
Subtask 2 (21pts)：n<=5000。
Subtask 3 (39pts)：无特殊限制。
对于全部数据，2<=n<=10^6 ，|ai|<=10^9 。

Solution

• 首先按照前缀 minmin 将序列分成若干段，显然每段是互不影响的。

• 对于每一段，我们只需要考虑最小值 xx 和最大值 yy 。

• 如果 y−x=f(a)y−x=f(a)，那么我们必须选择一个位置 ii ，

• 将 ii 之前的 xx 和 ii 之后的 yy 全部删去，这个用前后缀和做就好了。

• 时间复杂度 O(n)O(n) 。

Code

#include<cstdio> #include<cctype> using namespace std; const int N=1e6+5,inf=1e9; int ans,mn=inf,mx=-inf; int a[N],pre[N],suf[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline int max(int x,int y) {return x>y?x:y; } inline int min(int x,int y) {return x<y?x:y; } int main() {freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);int n=read();for(int i=1;i<=n;i++){a[i]=read();mx=max(mx,a[i]-mn);mn=min(mn,a[i]);}int now=1,fa=mx;mn=a[1];while(now<=n){int to=now;while(to<=n && a[to]>=mn) to++;mx=-inf;for(int i=now;i<to;i++) mx=max(mx,a[i]);if(mx-mn==fa){int sum=inf;pre[now-1]=0;for(int i=now;i<to;i++) pre[i]=pre[i-1]+(a[i]==mn);for(int i=to-1;i>=now;i--) suf[i]=suf[i+1]+(a[i]==mx);for(int i=now-1;i<to;i++) sum=min(sum,pre[i]+suf[i+1]);ans+=sum;}mn=a[now=to];}printf("%d",ans);return 0; }

总结

以上是生活随笔为你收集整理的JZOJ 5709. 【北大夏令营2018模拟5.13】数列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。