题目：这是一道来自搜狗初试的一道算法题，还算简单

给定一个序列，添加一定的元素使之成为回文数，并且是所有可能中元素之和最小的

例如 序列 {1 2 3} 我们可以添加变换为{3 2 1 2 3} {1 3 2 3 1} {1 2 3 2 1}… 其中最小的为{1 2 3 2 1}累加和为9

1
2
3
4
5
6
7
8
9
example

输入：

[1,2,3]

输出：

9

分析

遍历每个元素以每个元素为中心向两边扩张

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
//

/*#include "stdafx.h"*/
#include <iostream>
#include <climits>
using namespace std;


/*
@p: 输入的数组
@length：数组长度
@return：最小回文长度
*/
int find_min_sum(int p[],int length){
	unsigned short min = INT_MAX;
	for (int i = 0; i < length; i++)
	{
		unsigned short sum = 0;
		int left=i;
		int right=i;
		//找到以i为中心，左右第一个不等的
		while (--left>=0 && p[i]==p[left]);
		while (++right<length && p[i]==p[right]);
		//加上相等的元素
		sum+=(right-left-1)*p[i];
		//左右寻找并添加元素，使之成为回文，并累加
		while (left>=0 && right<length)
		{
			if(p[left]<p[right]){
				sum+=2*p[left];
				left--;
			}
			else if (p[left]>p[right]){
				sum+=2*p[right];
				right++;
			}
			else
			{
				sum+=2*p[right];
				left--;right++;
				
			}
		}
		//有一方到了边界，把另一方剩余元素，逆序放到另一方，并累加
		for (;right < length; right++)
		{
			sum+=2*p[right];
		}
		for (;left>= 0; left--)
		{
			sum+=2*p[left];
		}
		//找到最小值
		if (sum<min)
		{
			//cout<<sum<<endl;
			min=sum;
		}
	}
	//返回最小值
	return min;

}
void test1(){
	//已经是回文数了
	int a[6]={1,2,3,3,2,1};
	if(12==find_min_sum(a,6)) cout<<"test1 ok"<<endl;
}
void test2(){
	//所有数字不等
	int a[6]={1,2,3,4,5,6};
	if(36==find_min_sum(a,6)) cout<<"test2 ok"<<endl;
}
void test3(){
	//中间有重复元素
	int a[4]={1,3,4,3};
	if(12==find_min_sum(a,4)) cout<<"test3 ok"<<endl;

}

int main()
{
    //测试用例
	test1();
	test2();
	test3();

	return 0;
}

结果：

1
2
3
test1 ok
test2 ok
test3 ok