MODIFY SEQUENCE

xieyikai2333 · 2021-09-04 17:31:59 · 题解

一道SPOJ的水题

• 题目传送门

• 题目大意：给定组数 t，和每组数的个数 n，通过使相邻两个数同时减去一个自然数，使所有的数都为 0。

考虑数列中两个特殊的值：a_1 与 a_n。这两个数只有一个相邻的数，所以我们从 a_1 入手，a_n 用来判断。

对于从 2 到 n 的变量 i，用 a_i 减去 a_{i-1}，如果 a_i 为负，则直接否定可能性，退出循环。否则，如果最后 a_n 恰好为 0，则输出 YES，反之则输出 NO。

AC 代码：

#include <bits/stdc++.h>
using namespace std;
int a[10005];
int main()
{
    int t,n;
    bool flag;
    cin>>t;
    while(t--)
    {
        flag=true;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=2;i<=n;i++)
        {
            a[i]-=a[i-1];
            if(a[i-1]<0)
            {
                flag=false;
                break;
            }
        }
        if(flag&&a[n]==0)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

附上 AC记录