hdu5532

标签：int res 负数 序列 hdu5532 sc new

给定一个序列，询问是否能删除一个数让它成为非递减或者非递增的序列。

nlogn一直过不了，所以选择了以下方式。。。

因为删除一个嘛，先证明删除一个能不能是非递减的（非递增的把序列倒过来搞一次就行了）

首先，对一个序列前后两个数做差

比如说序列

3 1 4 1 5 做差后（即1-3,4-1,1-4,5-1）是 -2,3，-3,4。发现有2个负数，那就不行。

如果序列是 3 1 1 5。 做差后是-2,0，4。发现有一个负数，是在头部，可以删掉

如果序列是5 6 3 ,7 7，做差后是 1，-3,4,0。发现有一个负数，而且可以跟左右两边的某个数相加变成正数，那么这个3就可以删掉。

如果序列是1 2 3 4，做差后是1,1,1,1 没有负数，本身就可以是非递减。

能看得出来：

做差后的序列：如果有2个及以上负数，那它肯定不可能是非递减。

　　　　　　  如果有一个负数，它在头或者尾，或者在中间而且可以跟左右两边任意一个数相加是非负数，即可以是非递减

　　　　　　  如果没有负数，已经是非递减

时间复杂度是O（N），额外需要O（N）的空间存做差后的数组

非递增的话就把数组倒一下再来一次就行了。

https://www.cnblogs.com/Esquecer/p/9013331.html

import java.io.*;  

public class Main {
    public static int shu(int[] xx) {
        int[] res = new int[xx.length-1];
        for (int i = 1; i < xx.length; i++) {
            res[i-1] = xx[i]-xx[i-1];            
        }
        int cnt = 0;
        for (int i = 0; i < res.length; i++) {
            if (res[i]<0) {
                cnt++;
                if (cnt==1) {
                    if (i==0||i==res.length-1) {
                        continue;
                    }else {
                        if (res[i]+res[i-1]>=0 || res[i]+res[i+1]>=0) {
                            continue;
                        }else {
                            return 0;
                        }
                    }
                }
                if (cnt==2) {
                    return 0;
                }
            }            
        }
        return 1;
    }

    public static void main(String[] args)throws IOException {
        // TODO 自动生成的方法存根
        StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));      
        
        sc.nextToken();  //输入前记得加
        int n=(int)sc.nval;
        for (int i = 0; i < n; i++) {
            sc.nextToken();  //输入前记得加
            int nn = (int)sc.nval;
            int[] x1 = new int[nn];
            int[] x2 = new int[nn];
            for (int j = 0; j < nn; j++) {
                sc.nextToken();  //输入前记得加
                int yy = (int)sc.nval;
                 x1[j] = yy;                
            }
            for (int j = 0; j < nn; j++) {
                 x2[j] = x1[nn-1-j];                
            }
            int a1 = shu(x1);
            if (a1==1) {
                System.out.println("YES");
                continue;
            }
            int a2 = shu(x2);
            if (a2==1) {
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
        }
    }

}

 

标签：int,res,负数,序列,hdu5532,sc,new
From： https://www.cnblogs.com/xiaohuangTX/p/18239395