[CodeVS 3289]花匠

danihao123 posted @ 2016年7月15日 20:15 in 题解 with tags codevs 贪心 , 261 阅读
转载请注明出处:http://danihao123.is-programmer.com/

这破题吃枣药丸……

这题略加思索,就能发现最优策略是找转折点。但需要注意相等连块中也会存在转折点……并且,n<3时不要搬走花!

代码:

#include <cstdio>
const int maxn=100001;
int A[maxn];
int main(){
    int n;
    bool flag=false,tal;
    register int i,ans=0;
    scanf("%d",&n);
    if(n<3){
        printf("%d\n",n);
        return 0;
    }
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
    }
    for(i=1;i<=n;i++){
        if(i==1){
            ans++;
            continue;
        }
        if(A[i]!=A[i-1])
            flag=true;
        if(i==n){
            if(flag)
                ans++;
            break;
        }
        if(A[i]==A[i-1] && i>=2)
            A[i-1]=A[i-2];
        if((A[i]>A[i-1] && A[i]>A[i+1]) ||
           (A[i]<A[i-1] && A[i]<A[i+1]))
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter