愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

#牛客编程题#回文序列

如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如:
{1, 2, 1}, {15, 78, 78, 15} , {112} 是回文序列,
{1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是回文序列。
现在给出一个数字序列,允许使用一种转换操作:
选择任意两个相邻的数,然后从序列移除这两个数,并用这两个数字的和插入到这两个数之前的位置(只插入一个和)。
现在对于所给序列要求出最少需要多少次操作可以将其变成回文序列。

输入描述:

输入为两行,第一行为序列长度n ( 1 ≤ n ≤ 50)
第二行为序列中的n个整数item[i] (1 ≤ iteam[i] ≤ 1000),以空格分隔。

输出描述:

输出一个数,表示最少需要的转换次数

输入例子:

4
1 1 1 3

输出例子:

2

AC代码:

#include <iostream>
#include <cstdlib>
using namespace std;
int arr[1001];

int getAns(int arr[], int n) {
    int i = 0, j = n-1;
    int times = 0;
    // i, j为双指针,一个指向头,一个指向尾
    
    while(i <= j) {
        if(arr[i] == arr[j]) {
            ++i;
            --j;
        } else if(arr[i] > arr[j]) {
            for(; arr[j] < arr[i]; --j) {
                arr[j-1] += arr[j];
                arr[j] = 0;
                times++;
            }
        } else if(arr[i] < arr[j]) {
            for(; arr[i] < arr[j]; ++i) {
                arr[i+1] += arr[i];
                arr[i] = 0;
                times++;
            }
        }
    }
    
    if(arr[i] != arr[j]) times++;
    
    return times;
}

int main() {
    int n;
    scanf("%d", &n);
    
    for(int i=0; i<n; ++i) {
        scanf("%d", &arr[i]);
    }
    
    printf("%d\n", getAns(arr, n));
    
    return 0;
}