喂竹鼠

摘要:
为了科学高效地繁殖,小H决定在饲养时遵循两条规则:1。每只竹鼠应至少喂一块竹子。2.在相邻的竹鼠中,如果体重不同,较重的竹鼠必须喂更多的竹子。小H至少需要为竹鼠准备多少块竹子?在第一行输入整数N表示竹鼠数量,其中0<N≤50000;第二行中N的数量代表不同竹鼠的重量,用空格隔开,每个数量不超过50000只。
小H在吃过一次烤竹鼠之后,觉得非常美味,也动了自己养殖竹鼠的心思,正好家附近有很多竹子,于是在家旁建了个养殖场,他把养殖场隔出来N个隔间并且编好了号,每个隔间内养一只竹鼠。但竹鼠的特性非常奇怪,在喂食的时候,体重较大的竹鼠如果看到,左右相邻的隔间有竹鼠比它体重更轻却喂了更多的食物,大竹鼠就会心情郁闷而影响到它的健康。 
为了科学高效的养殖,小H决定喂食时遵循两个规矩:
1,每个竹鼠最少要喂1片竹子
2,相邻的竹鼠中,如果体重不同,则体重更高的竹鼠必须喂更多的竹子
请问小H最少需要为竹鼠们准备多少片竹子呢?

输入

第一行一个整数N,表示竹鼠数,其中0<N≤50000;
第二行N个数表示不同竹鼠的体重,以空格隔开,每个数不超过50000。

输出

输出一个数,表示最少需要准备的竹片数

样例输入 Copy

3
1 2 2

样例输出 Copy

4

提示

1. 样例1 解释:
一共有3只竹鼠,它们的体重分别是1 2 2
那么最少需要喂的竹片数量为1+2+1=4片

2. 数据范围
对于5%的数据,0<N≤10;
对于30%的数据,0<N≤2000;
对于100%的数据,0<N≤50000。
解析:该题要正反遍历两遍
本来想的是定义一个t,如果后面一个比前面一个大,就让t++,如果后面一个比前面一个小就把t变成1,sum+=t;但是如果序列为例如:(1 2 3 2 1)不对,
所以要正反便利两边;
AC代码:
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
typedef long long ll;
const int maxn = 1e6+10;
int a[maxn];
int b[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        b[i]=1;
    }
    for(int i=2;i<=n;i++){
        if(a[i]>a[i-1]){//正着先便利一边后一个比前一个大的 
            b[i]=b[i-1]+1;
        }
    }
    
    for(int i=n-1;i>=1;i--){
        if(a[i]>a[i+1]&&b[i]<=b[i+1]){//倒着便利前一个比后一个大的 
            b[i]=b[i+1]+1;
        }
    }
    
    ll sum=0;
    
    for(int i=1;i<=n;i++){
        sum+=b[i];
    }
    printf("%lld
",sum);
    return 0;
}

免责声明:文章转载自《喂竹鼠》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇看试卷父母的爱伴随着你一生,哪怕他们已经年迈下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章