[Jobdu] 题目1377：缓变序列

偏执的太偏执、 2021-12-03 07:31 80阅读 0赞

**题目描述：**

陈博在写论文时碰到一个难题：如何将给定的整数序列变换成缓变序列：即任意两个相邻的元素相差均为1，第1个元素和最后一个元素相差也为1. 变换是指改变原整数序列中各元素的顺序。例如整数序列1，3，2，2可以变换成缓变序列1，2，3，2. 其中（1，2）、（2，3）、（3，2）相差均为1，第1个元素和最后一个元素相差也为1.

陈博想了很长时间，纵然他英明神武，还是想让大家帮一个小忙：判断给定的整数序列能不能变换成缓变序列。

**输入：**

每个测试文件包含多个测试案例，每个测试案例两行，第一行包含一个整数N，代表原整数序列的长度，第二行是以空格隔开的N个整数，代表该整数序列。其中我们能保证2 <= N <= 10^5，每个整数大于等于1且小于等于10000.

**输出：**

对于每个整数序列，如果是缓变序列或者能够变换成缓变序列，输出YES，否则输出NO。

**样例输入：**

4
    1 3 2 2
    2
    1 1

**样例输出：**

YES
    NO

**答疑：**

解题遇到问题?分享解题心得?讨论本题请访问： [http://t.jobdu.com/thread-8100-1-1.html][http_t.jobdu.com_thread-8100-1-1.html]

1 #include <cstdio>
     2 #include <cstdlib>
     3 #include <cstring>
     4  
     5 int N;
     6 int A[10001];
     7  
     8 int main() {
     9     int tmp;
    10     while (scanf("%d", &N) != EOF) {
    11         memset(A, 0, sizeof(A));
    12         bool flag = false;;
    13         int min = 10000, max = 0;
    14         for (int i = 0; i < N; ++i) {
    15             scanf("%d", &tmp);
    16             ++A[tmp];
    17             min = min > tmp ? tmp : min;
    18             max = max > tmp ? max : tmp;
    19         }
    20         tmp = 0;
    21         for (int i = min; i <= max; ++i) {
    22             if (A[i] == 0) {
    23                 flag = false;
    24                 break;
    25             }
    26             tmp = A[i] - tmp;
    27             if (tmp <= 0 && i != max) {
    28                 flag = false;
    29                 break;
    30             } 
    31             if (tmp ==0 && i == max) { flag = true;}
    32         }
    33         if (flag) {
    34             printf("YES\n");
    35         } else {
    36             printf("NO\n");
    37         }
    38     }
    39     return 0;
    40 }
    41  
    42 /**************************************************************
    43     Problem: 1377
    44     User: hupo250
    45     Language: C++
    46     Result: Accepted
    47     Time:30 ms
    48     Memory:1060 kb
    49 ****************************************************************/

转载于:https://www.cnblogs.com/easonliu/p/4328681.html

[http_t.jobdu.com_thread-8100-1-1.html]: http://t.jobdu.com/thread-8100-1-1.html