3686. 回文串

你这贴的不完整吧。
我用java搞了一个，卡在8，超过2s（2.3s）

哪位大神看看怎么优化。（逻辑上，好像无法使用多线程，想不出优化方法了）

import java.util.Scanner;

public class MyP2 {
public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    while(sc.hasNext())
    {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        //两头判断，小部先合并
        int head=0, tail = n-1;
        int times = 0;
        while(head<tail)
        {
            if(arr[head]>arr[tail])
            {
                //tail部分合并
                arr[tail-1] += arr[tail];
                tail--;
                times++;
            }else if(arr[head]<arr[tail])
            {
                //head部合并
                arr[head+1] += arr[head];
                head++;
                times++;
            }else
            {
                head++;
                tail--;
            }
        }
        System.out.println(times);
    }
    sc.close();
}

}

花了大半天，使用了n多种脑残的办法，最终想到一个很简单的办法实现了。
最后卡在第66题，把所有变量从int变为long long就通过了。

include

using namespace std;
long long k;
long long up,down;
int main()
{

long long count;
cin>>down;
long long *kkk=new long long[down];
for(k=0;k<down;k++)
cin>>kkk[k];
up=0;
count=0;

//1 3 2 1 4 5 6 7 5 5 1
//for(k=0;k<n;k++)cout<<kkk[k]<<” “;cout<{if(kkk[up]>kkk[down])
{
//cout<<”kkk[“<<i<<”]>kkk[“<<n-i-1<<”]”<<endl;//测试输出2
kkk[down-1]=kkk[down]+kkk[down-1];

down=down-1;count++;

//for(k=0;k<n;)cout<<kkk[k++]<<" ";cout<<endl;//测试输出4
}

else if(kkk[up]<kkk[down])
{
//cout<<”kkk[“<<i<<”]<kkk[“<<n-i-1<<”]”<<endl;//测试输出5
kkk[up+1]=kkk[up]+kkk[up+1]; //cout<<”kkk[“<<i<<”]=”<<kkk[i]<<endl;//测试输出6

    //cout<<"kkk["<<k<<"]="<<kkk[k]<<endl;//测试输出7
up=up+1;count++;  
//for(k=0;k<n;k++) cout<<kkk[k]<<" ";cout<<endl;//测试输出8

}

else if(up>=down) break;
else if(kkk[up]==kkk[down])

}

cout<<count;
return 0;
}

基本思路是贪心算法：每次比较最左和最右，如果相等就继续比较内部的元素，如果最左小于最右就合并最左边两个元素，反之合并最右边两个元素（这样合并次数最少）

input()
a_s = input().split()
a = []
for s in a_s:
a.append(int(s))
left = 0
right = len(a) - 1
times = 0
while left < right:
if a[left] == a[right]:
left += 1
right -= 1
elif a[left] < a[right]:
left += 1
a[left] = a[left] + a[left - 1]
times += 1
else:
right -= 1
a[right] = a[right] + a[right + 1]
times += 1
print(times)

我也是测试66卡住，测试跑的是什么，只是将hash[]的int改成了long就通过了，要求在0到1e9之间，int应该可以满足，求解？？

include

long hash[1000000];

int main(void){
int n;
for (int i = 0; i < 1000000; i++) {
hash[i]=0;
}
while(scanf(“%d”,&n)!=EOF)
{
int l=0;
int r=n-1;
int num=0;
for (int i = 0; i < n; i++) {
scanf(“%d”,&hash[i]);
}
while(l<r)
{
if(hash[l]hash[r])
{
num++;
hash[r-1]=hash[r]+hash[r-1];
r–;
}
else
{
l++;
r–;
}
}
//判断是否成功回文，并输出num，或者返回-1
if(hash[l]==hash[r])
printf(“%d\n”,num);
else
return -1;
}
return 0;
}