2009-12-07 19:01:01來源不明

等值首尾和

作法 : 名題百則的標準做法

我有點懶了  所以直接照打  做法應該不難懂

/***************************************************************/

#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;
}

上一篇:整數編號輸出

下一篇:矩形中的幾何

crazy小螃蟹 2011-09-28 17:43:46

#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);
}

x000032001 2010-09-19 12:01:25

我認為那份程式碼有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;
}
}