随机算法：呵呵，声明这篇里我们不谈科学的严谨，下面这道题听别人说用DF，DP等，我不知道怎 么DP，DF。因此弄了个随机数，随机分配硬币，当然也要用点小技巧，开始随机次数太 大搞了几次 Time Limit Exceeded，最后恼火了开了 100，我靠 ，这次 Wrong Answer，最后一 次了我搞了个 1000 ，终于 Accepted ！这主要是在比赛的时候，如果实在没办法做，可以尝试用随机算法，运气好一次就可以Accepted ，当然也不排除永远不能 Accepted，主要看它的测试数据强不强了。呵呵，这样太没技术含量了，哪位朋友如果有好的解决办法，贴出来分享下啊 ！ 分硬币  一个背包里面最多有100枚硬币，要将这些硬币分给两个人，使得两人得到的钱差距最小 。每枚硬币的面值范围是1分到500分，不允许将一枚硬币分开。  Input 第一行有一个非负整数m（m<=100），表示硬币数。第二行有m个正整数，表示每枚硬币 的面值，中间用空格分开。  Output 每组仅输出一个非负整数，表示两人所分到钱的最小差值。  Sample Input 32 3 541 2 4 6  Sample Output 01  #include <stdio.h>#include <stdlib.h>#include <time.h>#include <string.h> #define TIMES 1000int mycmp(const int*a,const int*b){ if(*a > *b)  return 1; if(*a < *b)  return -1; return 0;}int    main(){  int i,j,a[110],asave[110],min; int suma,sumb,k,t;  while(scanf("%d",&i) != EOF){  for(j = 0; j < i; j++)   scanf("%d",&a[j]);        memcpy(asave,a,sizeof(int)*i);  qsort(a,i,sizeof(int),mycmp);  for(min = 10000,j = 0; j < TIMES; j++){   for(suma = sumb = k = 0; k < i; k++){    t = rand()%i;    if(a[t] == -1){     for(t = 0; a[t] == -1; t++)      ;    }    if(sumb > suma)     suma += a[t];    else     sumb += a[t];    a[t] = -1;   }   memcpy(a,asave,sizeof(int)*i);   t = (suma > sumb ? suma-sumb : sumb - suma);   if(t < min)    min = t;  }  printf("%d\n",min); } return 0; }

评论