出题.cpp

很好的搜索： 给你很多长度不定的木棒

#include<iostream>
#include<algorithm>
#include <stdlib.h>
using namespace std;
int stick[100];
int used[100];
int n, k, max1;
void init ( int n )//初始化used数组
{
	
	used[0] = 1;
	for ( int i=1; i<n; i++ )
	{
		used[i] = 0;
	}
}

bool  cmp(int a,int b)
{
	if(a>b)
	return 1;
	return 0;
}

int dfs ( int start, int no, int cur, int last, int allsum )//深度优先搜索的主题函数，
                                                           //和STICKS基本一样，
{
	
	int i, j;
	
	if ( no == k )                 
	{
		if ( allsum < max1 - cur )  
		{
			return 0;
		}
		return 1;
	}
	
	if ( cur >= max1 )
	{
		if ( k - no > last )
		{
			return 0;
		}
		if ( max1*(k-no) > allsum )
		{
			return 0;
		}
		
		for ( i=1; i<n; i++ )
		{
			if ( ! used[i] )
			{
				break;
			}
		}
		used[i]= 1;
		if ( dfs ( i+1, no+1, stick[i], last-1, allsum-stick[i] ) )
		{
			return 1;
		}
		used[i] = 0;
		return 0;
	}
	else
	{
		if ( k-no > last - 1 )
		{
			return 0;
		}
		if ( max1*(k-no)+max1-cur > allsum )
		{
			return 0;
		}
		
		for ( i=start; i<n; i++ )
		{
			if ( ! used[i] )
			{
				used[i] = 1;
				if ( dfs ( i+1, no, cur+stick[i], last-1, allsum-stick[i] ) )
				{
					return 1;
				}
				used[i] = 0;

				for ( j=i+1; j<n; j++ )
				{
					if ( stick[j] != stick[i] )
					{
						break;
					}
				}
				i = j - 1;
			}
		}
		return 0;
	}
}

int main ()
{
	
	int sum;
	
	while ( scanf ( "%d%d", &n, &k ) != EOF )
	{
		
		sum = 0;
		for ( int i=0; i<n; i++ )
		{
			scanf ( "%d", &stick[i] );
			sum += stick[i];
		}
		
		//qsort ( stick, n, sizeof ( int ), cmp );
		sort(stick,stick+n,cmp);
		max1 = sum / k + 1;//计算木棒最大可能的长度
		init ( n );       //初始化used数组
		while (  -- max1 )//从大到小遍历木棒的长度
		{
			if ( dfs ( 1, 1, stick[0], n-1, sum-stick[0] ) )//进行深搜
			{
				break;
			}
		}
		
		printf ( "%d\n", max1 );
		
	}
	return 0;
}