JZOJ5709. 【北大夏令营2018模拟5.13】数列

 发布日期:2018-11-14 12:59:13  阅读次数:阅读数:183  来源:

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 。

题解

先看f(a)是什么,
就是每个位置减去前面的最小值,然后这些东西取个max。
那么对于原序列f(a)可以算出来。

因为每个位置都是减去前缀的min,而前缀min是一段一段的,
所以就可以根据前缀min的值进行分段。
很显然,每一段都是独立的。
现在就对前缀min相同的一段进行处理,
在这一段里面可能有多个最大值,
那么就可以枚举一个分界点,
将这个位置前面全面的最小值修改,这个位置后的全面最大值修改,
这样修改之后,这一段的f(a)值就已经不是原来的f(a)值了,
每一段都这样做,最后的f(a)值也就自然改变了。

code

#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <time.h>
#define ll long long
#define N 100003
#define M 103
#define db double
#define P putchar
#define G getchar
#define inf 998244353
#define pi 3.1415926535897932384626433832795
using namespace std;
char ch;
void read(int &n)
{
    n=0;
    ch=G();
    while((ch<'0' || ch>'9') && ch!='-')ch=G();
    ll w=1;
    if(ch=='-')w=-1,ch=G();
    while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
    n*=w;
}

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
ll abs(ll x){return x<0?-x:x;}
ll sqr(ll x){return x*x;}
void write(ll x){if(x>9) write(x/10);P(x%10+'0');}

int n,m,a[N],mi[N],ans,t,sum,mx,nxt,s[N]; 

int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);

    read(n);mi[0]=2147483647;
    for(register int i=1;i<=n;i++)
    {
        read(a[i]);
        mi[i]=min(mi[i-1],a[i]);
        mx=max(mx,a[i]-mi[i]);
    }
    for(int i=1;i<=n;i=nxt)
    {
        s[i]=1;t=2147483647;m=mi[i]+mx;sum=0;
        for(nxt=i+1;mi[nxt]==mi[i] && nxt<=n;nxt++)s[nxt]=s[nxt-1]+(a[nxt]==mi[nxt]?1:0);
        for(register int j=nxt-1;j>=i;j--)
        {
            t=min(t,sum+s[j]);
            if(a[j]==m)sum++;
        }
        ans+=min(t,sum);
    }
    printf("%d",ans);
    return 0;
}
如果您有好的新闻与建议,欢迎点击文章投稿

    发表评论

    电子邮件地址不会被公开。

  • 内容

  • 网名