时间限制：1s 内存限制：32MB

问题描述

回文串是一个正读和反读都一样的字符串，比如level或者noon就是回文串。回文数组也是如此，比如[100,200,100]或者[178,256,256,178]就是回文数组，[1,2,3]和[100,200]不是回文数组。

现在yyy有一个数组，他想仅仅通过合并操作将数组转换为回文数组，

合并操作：将数组中相邻两个的数合并为一个数，合并后的数为合并前两个数的和。例如[1,2,3]通过一次合并操作即可变成回文数组[3,3]。

输入描述

第一行一个整数T(1≤T≤10)表示数据组数。

对于每组数据第一行一个整数n(1≤n≤〖10〗^5)，表示数组的长度。

第二行n个整数A_1,A_2,…,A_n (1≤A_i≤10000)分别表示数组中的每个数。

输出描述

对于每组数据输出一行：一个整数表示最少的合并次数。

输入样例

1

3

1 2 3

输出样例

1

【题目链接】:

【题解】



用两个指针，哪个指针指的数字小；则那个指针往中间的方向合并(相邻的);

如果数字相同则两个指针都往中间靠;



【完整代码】

#include <bits/stdc++.h>

#define rep1(i,a,b) for (int i = a;i <= b;i++)

using namespace std;

#define pb push_back;

long long num[100005];

int main()

{

    //freopen("D:\\rush.txt","r",stdin);

    ios::sync_with_stdio(false);

    long long t,n;

    long long ans;

    cin>>t;

    while(t--)

    {

        cin>>n;

        ans = 0;

        for(int i=1;i<=n;i++)

        {

            cin>>num[i];

        }

        int l = 1,r = n;

        while(1)

        {

            if(num[l]<num[r])

            {

                num[l+1] = num[l]+num[l+1];

                l++;

                ans++;

            }

            else

            if(num[r]<num[l])

            {

                num[r-1] = num[r] + num[r-1];

                r--;

                ans++;

            }

            else

            {

                l++;

                r--;

            }

            if(l>=r) break;

        }

        cout<<ans<<endl;

    }

    return 0;

}