九度称号1377：缓变序列

转载本文，请注明链接 http://blog.csdn.net/yangnanhai93/article/details/40474355

题目链接地址：http://ac.jobdu.com/problem.php?

这道题目的难点在于怎样分析出缓变序列的特征：

1：缓变序列排序之后必须连续

证明：如果排序之后的序列为a[1] a[2] a[3]... a[n]。当中a[n]-a[n-1]>1，即an与前面的数不连续，由于缓变序列要求不论什么一个数的前后的变化都是1，然而对于a[n]。没有不论什么一个数能够在其前后使得满足缓变序列的性质，所以排序之后数组必须是连续的

2：缓变序列应当满足的要求是构成一个新的数组记为数组A，该数组具有例如以下性质：

A[1]=a1,A[n]=an-A[n-1].对于1-n的A[n]，须要满足A[n]=0。且1-(n-1)时： A[n]>0 （A数组表示的意思就是还剩下多少个位置须要填补）

证明：对于1-（n-1)，记为m时。假设A[m]<=0，此时，可以得到如若A[m]=0。恰好得到一个缓变序列。假设A[m]<0，则说明m的个数少于m-1位须要的，则肯定不能满足要求

对于n位。正如上面说明A[n]=0，使得缓变序列的须要填补的数恰好满足。

以下用图的方式来帮助理解，通过画线，非常明显知道必须是上一层的点必须大于下一层的点的数目(最后一层除外)，也必须满足A[n]=0

#include <iostream>
#include <memory.h>
using namespace std;
int main()
{
    //freopen("data.in","r",stdin);
    int num,A[10001],tmp,low,high;
    while(cin>>num)
    {
        memset(A,0,sizeof(A));
        for(int i=0;i<num;i++)
        {
            cin>>tmp;
            A[tmp]++;
        }
        low=0;
        while(A[low]==0)
            low++;
        tmp=0;
        high=low;
        while(A[high]!=0)
        {
            tmp+=A[high];
            high++;
        }
        if(num==tmp)
        {
            bool isTrue=true;
            tmp=0;
            for(int i=low;i<high-1;i++)
            {
                tmp=A[i]-tmp;
                if(tmp<=0)
                {
                    isTrue=false;
                    break;
                }
            }
            if(A[high-1]-tmp)
                isTrue=false;
            if(isTrue)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        else
            cout<<"NO"<<endl;
 
    }
 
    return 0;
}
/**************************************************************
    Problem: 1377
    User: vincent_ynh
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:1520 kb
****************************************************************/

九度 称号1377：缓变序列

九度称号1377：缓变序列