等值首尾和
作法 : 名題百則的標準做法
我有點懶了 所以直接照打 做法應該不難懂
/***************************************************************/
#include<stdlib.h>
#include<stdio.h>
int N,a,NUM[100000];
int H(int N,int NUM[])
{
int prefix=0,suffix=0;
int prefix_idx=0,suffix_idx=N-1;
int T=0;
while(suffix_idx>=0 && prefix_idx<=N-1)
{
if(prefix<suffix)
prefix+=NUM[prefix_idx++];
else if(prefix>suffix)
suffix+=NUM[suffix_idx--];
else
T++,prefix+=NUM[prefix_idx++],suffix+=NUM[suffix_idx--];
}
return T;
}
main()
{
while(scanf("%d",&N)==1)
{
for(a=0;a<N;a++)
scanf("%d",&NUM[a]);
printf("%d\n",H(N,NUM));
}
return 0;
}
我認為那份程式碼有BUG
第一次進入while迴圈由於
prefix=0,suffix=0
剛好這份空集合會變成一組解
但是pre的全部相加和suf的全部相加卻不會計算到
而我的程式碼一開始就把pre賦值為第一個元素
suf為最後一個 DEBUG很久才發現
後來我改成這樣在ZJ上AC
int main()
{
int a;
while( cin >> a )
{
int *data = new int[100001];
for( int i = 0 ; i<a ; ++i )
{
cin >> data[i];
}
cin.get();
int j = a-1 ,i = 0;
int pre = data[i++] , suf = data[j--] , out = 0;
while( i<=a-1 || j>=0 )
{
//cout << " before pre = " << pre << " suf = " << suf << " i = " << i << " j = " << j << " out = " << out << endl;
if( pre > suf )
{
suf += data[j--];
}
else if ( pre < suf )
{
pre += data[i++];
}
if(pre==suf)
{
out++;
pre += data[i++];
suf += data[j--];
}
//cout << " after pre = " << pre << " suf = " << suf << " i = " << i << " j = " << j << " out = " << out << endl;
//cin.get();
}
cout << out << endl;
delete []data;
}
}
#include <stdio.h>
using namespace std;
int main(){
int n, i, j, c, s, a[100000];
scanf ("%d", &n);
for (i = 0; i < n; i++) scanf ("%d", &a[i]);
for (c = i = 0, j = n - 1, s = a[i] - a[j]; ~j; c++, i++, j--, s = a[i] - a[j])
while (s) s += (s < 0 ? a[++i] : -a[--j]);
printf ("%d\n", c);
}