题目大意：将n节木棒接成m个长度相等的木条，要求木条的长度尽可能的短
#include <bits/stdc++.h> using namespace std; #define LL long long #define LD long double #define SC(t,x) static_cast<t>(x) #define AR(t) vector < t > #define PII pair < int, int > #define PLL pair < LL, LL > #define PIL pair < int, LL > #define PLI pair < LL, int > #define PQ priority_queue #define GT(type) greater < type > #define MP make_pair #define PB push_back #define PF push_front #define POB pop_back #define POF pop_front #define PRF first #define PRS second #define fr(x) freopen(x,"r",stdin) #define fw(x) freopen(x,"w",stdout) #define INIT(ar,val) memset ( ar, val, sizeof ( ar ) ) #define FORD(loop,start,end) for( int loop = start; loop < end; ++loop ) #define FFORD(loop,start,end) for( int loop = start; loop > end; --loop ) #define FOR(loop,start,end) for( int loop = start; loop <= end; ++loop ) #define FFOR(loop,start,end) for( int loop = start; loop >= end; --loop ) #define qmax(a,b) (((a)>(b))?(a):(b)) #define qmin(a,b) (((a)<(b))?(a):(b)) #define qabs(a) (((a)>=0)?(a):(-(a))) const int INF = 0x3fffffff; const int SINF = 0x7fffffff; const long long LINF = 0x3fffffffffffffff; const long long SLINF = 0x7fffffffffffffff; using namespace std; const int maxn=100; int n,ans,sum; int a[maxn],vis[maxn]; bool cmp(int a,int b) {return a>b;} int f1(int x) { if(sum % x == 0 && (sum / x) >= a[0]) return 1; return 0; } bool dfs(int cnt,int pos,int sum) { if(cnt == n) return true; for(int i = pos; i < n; i++) { if(vis[i]) continue; if(sum + a[i] < ans) { vis[i] = 1; if (dfs(cnt + 1, i + 1, sum + a[i])) return true; vis[i] = 0; } else if (sum + a[i] == ans) { vis[i] = 1; if (dfs(cnt + 1, 0, 0)) return true; vis[i] = 0; return false; } if (sum == 0) return false; } return false; } int main() { // fr("input.txt"); while(~scanf("%d", &n)) { if(n==0) break; memset(a,0,sizeof(a)); sum=0; for(int i = 0; i < n; i++) { scanf("%d",&a[i]); sum+=a[i]; } sort(a,a+n,cmp); for(int i=n;i>0;--i) { if(!f1(i)) continue; ans=sum/i; memset(vis,0,sizeof(vis)); if(dfs(0,0,0)) { printf("%d\n",ans); break; } } } return 0; }