題干：

Professor Zhang has kinds of characters and the quantity of the?ii-th character is?aiai. Professor Zhang wants to use all the characters build several palindromic strings. He also wants to maximize the length of the shortest palindromic string.?

For example, there are 4 kinds of characters denoted as 'a', 'b', 'c', 'd' and the quantity of each character is?{2,3,2,2}{2,3,2,2}?. Professor Zhang can build {"acdbbbdca"}, {"abbba", "cddc"}, {"aca", "bbb", "dcd"}, or {"acdbdca", "bb"}. The first is the optimal solution where the length of the shortest palindromic string is 9.?

Note that a string is called palindromic if it can be read the same way in either direction.?

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:?

The first line contains an integer?nn?(1≤n≤105)(1≤n≤105)?-- the number of kinds of characters. The second line contains?nn?integers?a1,a2,...,ana1,a2,...,an?(0≤ai≤104)(0≤ai≤104).

Output

For each test case, output an integer denoting the answer.

Sample Input

4 4 1 1 2 4 3 2 2 2 5 1 1 1 1 1 5 1 1 2 2 3

Sample Output

3 6 1 3

題目大意：

現在這個數組a里有一些字符，第i個字符的數量是a[i]。巨巨想用這些字符來構造一些回文串好讓他的程序通過編譯。

他想知道各種組合方案中最短字符串長度的最大值。

舉個栗子：

現在有 ‘a’, ‘b’, ‘c’, ‘d’?四種字符并且他們的數量是?{2,3,2,2}?巨巨可以構造出{?“acdbbbdca”}, {?“abbba”,?“cddc”}, {?“aca”,?“bbb”,?“dcd”},或{“acdbdca”, “bb”}?四種方案.

在以上方案中，第一個方案的最短字符串長度比其他三種方案中的最短字符串長度都長，為9。

?

解題報告：

? ? ? ? 奇數字符串單獨處理一下。（可以證明回文串中，如果有的話，奇數字符，只能有一個。）

AC代碼：

#include<cstdio> #include<queue> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #define ll long long using namespace std; int main() {ll t,n,x;cin>>t;while(t--) {scanf("%lld",&n);ll ji = 0,ou=0,sum=0;for(int i = 1; i<=n; i++) {scanf("%lld",&x);if(x & 1) ji++;sum+=x/2;}if(ji == 0) printf("%lld\n",sum*2);else printf("%lld\n",2*(sum/ji)+ 1);//不加括號不對}return 0; } #include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int ji,ou,all,n; int main() {int t;cin>>t;while(t--) {ji=ou=all=0;cin>>n;for(int tmp,i = 1; i<=n; i++) {scanf("%d",&tmp);if(tmp&1) ji++,all+=(tmp-1)>>1;else all+=tmp>>1;}if(ji==0) printf("%d\n",all<<1);else printf("%d\n",(all/ji)*2+ 1);} return 0 ;}

總結

以上是生活随笔為你收集整理的【HDU - 5744 】Keep On Movin （回文串性质，贪心思维，不是水题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。