• P3929 SAC E#1


    P3929 SAC E#1 - 一道神题 Sequence1

    2017-10-07


    题目背景

    小强和阿米巴是好朋友。


    题目描述

    小强很喜欢数列。有一天,他心血来潮,写下了一个数列。

    阿米巴也很喜欢数列。但是他只喜欢其中一种:波动数列。

    一个长度为n的波动数列满足对于任何i(1 <= i < n),均有:

    a[2i-1] <= a[2i] 且 a[2i] >= a[2i+1](若存在) 或者

    a[2i-1] >= a[2i] 且 a[2i] <= a[2i+1](若存在)

    阿米巴把他的喜好告诉了小强。小强便打算稍作修改,以让这个数列成为波动数列。他想知道,能否通过仅修改一个数(或不修改),使得原数列变成波动数列。


    输入输出格式

    输入格式: 

    输入包含多组数据。

    每组数据包含两行。

    第一行一个整数n表示数列的长度。

    接下来一行,n个整数,表示一个数列。

    输出格式:

    对于每一组输入,输出一行Yes或No,含义如题目所示。


    输入输出样例

    输入样例#1:
    5
    1 2 3 2 1
    5
    1 2 3 4 5
    
    输出样例#1:
    Yes
    No

    说明

    对于30%的数据,n <= 10

    对于另外30%的数据,m <= 1000

    对于100%的数据,n <= 10^5,m <= 10^9

    其中m = max|a[i]|(数列中绝对值的最大值)


    w普及组模拟赛翻车了~(≧▽≦)/~啦啦啦

    暴力+模拟=AC  TAT

    可以发现如一个数要被修改,则将其改为 ∞ 或 −∞ 一定不 会比修改为别的数不优。

    由于波动序列本质上只有 2 种,所以对于每一种波动序列, 求出将原序列变为这种波动序列最少需要修改几次。如果两 个值的较小值不大于 1,则输出"Yes",否则输出"No"。 问题变为求原序列变为某种波动序列需要的最小修改次数

    从前向后扫,如果遇到某个元素不满足要求,则将该元素修 改为 ∞ 和 −∞ 中满足要求的那个,并将计数器加一。

    暴力查看上一次的last,不满足就把当前的改成∞ 或 −∞。直接判断计数器是否小于1就可以了。

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    #define ll long long
    using namespace std;
    const int maxn=1e5+2333;
    const int INT=1e9+233;
    inline int read(){
        int an=0,f=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while('0'<=ch&&ch<='9'){an=an*10+ch-'0';ch=getchar();}
        return an*f;
    }
    int n;
    int a[maxn];
    int main(){
        while(cin>>n){
            for(int i=1;i<=n;i++)a[i]=read();
            int tot1=0,tot2=0;
            int last1=-INT,last2=INT;
            int flag=1;
            for(int i=1;i<=n;i++){
            flag^=1;
                if(flag){
                    if(last1>=a[i]){//下降 
                    last1=a[i];}
                    else{
                        last1=-INT;tot1++;//到最低 
                    }
                    if(last2<=a[i]){//
                    last2=a[i];
                    }
                    else {
                        last2=INT;tot2++;
                    }
                }
                else {
                    if(last1<=a[i]){
                        last1=a[i];}
                    else{
                        last1=INT;tot1++;}
                    if(last2>=a[i]){
                        last2=a[i];
                    }
                    else {
                        last2=-INT;tot2++;
                    }
                }
            }
            if(tot1<=1||tot2<=1)cout<<"Yes
    ";
            else cout<<"No
    ";
        }
        return 0;
    }
    P3929 SAC E#1 - 一道神题 Sequence1

    by:s_a_b_e_r


  • 相关阅读:
    持续集成 自动化构建、测试、部署您的Coding代码
    MySQL主从 常见的错误及解决方案
    老王带你走过 Kafka 入门教程
    Spring Cloud Eureka 常用配置及说明
    关于智慧大数据中心平台建设思路
    工作经验是积累总结出来的
    程序员晋级CTO之路的8大准则
    Spring Cloud Feign 使用方法与性能优化
    Elasticsearch(ES)API 增删查改常用操作
    ELK 日志采集 实战教程
  • 原文地址:https://www.cnblogs.com/ck666/p/7635850.html
一二三 - 开发者的网上家园