#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

#define MAX_ROUTE 5000 + 5
int tot;
int n;
int time[60];
typedef struct
{
		int initial;
		int interval;
		int times;
}ST_Route;

ST_Route stRoute[MAX_ROUTE];
int ans;
initVar()
{
		memset((char *)&time, 0, sizeof(time));
		memset((char *)&stRoute, 0, sizeof(stRoute));
		tot = 0;
		ans = 17;

}

int cmpStruct(const void *a, const void *b)
{
		ST_Route *p = (ST_Route *)a;
		ST_Route *q = (ST_Route *)b;
		return  q->times - p->times;

}

int check(int init, int inter)
{
		int i;

		for(i = init+inter; i<60; i = i+inter)
		{
				if(0 == time[i])
						return 0;
		}
		return 1;
}

int findRoute()
{

		int i, j; 
		int init = 0; 
		int inter = 0;
		int iTemp = 0;

		for(i = 0; i<=29; i++)
		{
				if(time[i] == 0)
						continue;

				init = i;

				for(j = 2*i+1; j<60; j++)
				{
						inter = j-init;	

						iTemp = check(init, inter);

						//						printf("init = %d, inter = %d, iTemp = %d\n", init, inter, iTemp);
						if(iTemp == 1)
						{
								stRoute[tot].initial = init;
								stRoute[tot].interval = inter;
								stRoute[tot].times = (59 -init)/inter + 1;
								tot++;
						}
				}
		}
}

void dfs(int start, int num)
{
		int i, j;

		//		printf("start= %d, num = %d, tot = %d ans = %d, n = %d\n", start, num, tot, ans, n);
		if( n<=0 )
		{
				if(num<ans)
						ans = num;

				return;
		}

		for(i = start; i<tot; i++)
		{

				//				printf("num = %d, n/stRoute[i].times = %d, ans = %d, i = %d, tot = %d, n = %d\n", num , n/stRoute[i].times, ans,i, tot, n);
				if(num + n/stRoute[i].times>=ans ) // 这一行剪枝太厉害了。。。。, 一定要注意求最小。最大之类的东西。都是可以把max，min来作为剪枝的条件的。
						return;
				if(1 == check(stRoute[i].initial, stRoute[i].interval))	
				{
						for(j = stRoute[i].initial; j<60; j += stRoute[i].interval)
						{

								time[j]--;
								n--;
						}
						dfs(i, num+1);
						for(j = stRoute[i].initial; j<60; j += stRoute[i].interval)
						{
								time[j]++;
								n++;
						}
				}
		}
}


int main()
{
		int i = 0, iTemp = 0;

		while(scanf("%d", &n)!=EOF)
		{

				//				printf("n = %d\n", n);

				initVar();
				for(i = 0; i<n; i++)
				{
						scanf("%d", &iTemp);
						//						printf("i = %d, iTemp = %d\n",i, iTemp);
						time[iTemp]++;
				}

				findRoute();

				qsort(stRoute, tot, sizeof(ST_Route), cmpStruct);

				//				for(i = 0; i<tot; i++)
				//				{
				//						printf("why i = %d, stRoute[i].initial = %d, stRoute[i].interval = %d, stRoute[i].times = %d\n", i,stRoute[i].initial, stRoute[i].interval, stRoute[i].times );
				//				}

				dfs(0, 0);

				printf("%d\n", ans);
		}

}

• Re:抄的一个大神的。然后。大神的代码能过。我不行。我已经wa 10多次了。跪求数据。跪求大神指出来哪里错误了 (27) 274856653 2019-09-18 15:42:46