Question

acm pku 1011 自己测试的时候结果都是对的,但是在poj上通不过,求高手解答.[附源码]

#include <iostream>
#include <stdlib.h>
using namespace std;
int stick[100];
int used[100];
int ns;
int len;
int ok;
int cmp(const void *a,const void *b)
{
int a1 = *(int *)a;
int a2 = *(int *)b;
return a2 - a1;
}
int sum(int num)
{
int adds = 0;
for(int i = 0 ;i<num;i++)
{
adds += stick[i];
}
return adds;
}

bool s(int ns,int len,int num)
{
int i =0;
int temp=0;
for(i = 0;i<num;i++)
{
if(used[i]==0)
{
if(temp + stick[i] < len)
{
temp += stick[i];
used[i] = 1;
}
if(temp + stick[i] == len)
{
used[i] = 1;
return 1;
}
}
}
return 0;
}

int main()
{
int num;
int slen;
while(cin>>num)
{

ok = 1;
if (num == 0)break;
for(int i =0 ;i<num;i++)
{
cin >> stick[i];
}
qsort(stick,num,sizeof(int),cmp);
slen = sum(num);
for(int i=stick[0];i<=slen;i++)
{
if(slen % i == 0)
{
ns = slen / i;
len = i;
memset(used,0,sizeof(used));
int j ;
for (j = 0 ; j < ns ; j++)
{
if(!s(ns,len,num))
{
break;
}
}
if(j == ns)
{
cout<< len<<endl;
break;
}
}
}
}
return 1;
}

Answer 1

9
15 4 3 1 2 8 11 8 8
这个就不对嘛

追问

多谢。请问我的这种方法，逻辑错在哪里？应该如何分析才是对的呢?

Answer 2

dfs写成了贪心