POJ 1012:Joseph 我做出来了，但是放在POJ上肯定会超时

你如果要看题，请走这个link:

下面是我的非常笨拙的算法，之所以这样说，是知道它放在POJ上肯定是超时，不过还是可以高兴下，理由很多，因为首先这是一个能够得出正确结果的答案，其次每一行都是自己写的，可以看出来算法、优化之类懂的东西很少，为了提高在POJ上的排名，我决定打表通过。函数进出栈次数多了，肯定影响性能，不过我的确没有那伙神通聪明，也没那么好记忆力，慢慢来吧！当前排名37823。

 

#include<stdio.h>
#define LEN 13 //1~13

int cycle[26];
int cur_pos;

void display();
int init_cycle(int);
void seek_one_alive_person(int);
int kill_one_person(int,int);
int seek_interval(int,int);
void seek(int nums);
int main(void)
{
  int i=0,num,nums_good[LEN];
  while(1)
  {
    scanf("%d",&num);
    if(num==0)
      break;
    else
      nums_good[i++]=num;
  }
  nums_good[i]=0;
  i = 0;
  while(nums_good[i]!=0)
  {
    // printf("seek %d\n",nums_good[i]);
    seek(nums_good[i]);
    ++i;
  }
  return 0;
}

void seek(int nums)
{
  int interval = 1 ; //处决的间隔，使用蛮力法去探测，从1开始数，直到这个interval不会在杀光坏人之前，杀了任何一个好人
  int ret;
  while(1)
  {
    // printf("now interval is %d\n",interval);
    //seek_interval如果返回0，表示邪恶的interval,如果返回1，表示善良的interval
    init_cycle(nums);
    cur_pos = -1 ;
    //printf("Init Cycle is : ");
    //display();
    ret = seek_interval(interval,nums);
    ++interval;
    if(ret == 0)
      continue;
    else
      break;
  }
   printf("%d\n",interval-1);
}

int seek_interval(int interval,int nums)
{

  int nums_bad_alive = nums;
  int good_killed = 0 ; //0表示好人没有被杀，1表示好人被杀了
  while(nums_bad_alive>0) //如果坏人没有杀完就必须杀下去，如果将杀好人，马上跳出循环，报告这个interval是邪恶的
  {
    //去杀人吧，
    good_killed = kill_one_person(interval,nums);
    if(good_killed == 1)
      return 0;
    else if (good_killed == 0)
    {
      --nums_bad_alive;
      // cur_pos++;
    }
    // printf("there is %d bad person alive\n",nums_bad_alive);
  }
  //printf("there is %d bad person alive\n",nums_bad_alive);

  return 1;
}

int kill_one_person(int interval, int nums)//现在的问题是kill one person始终返回1
{
  /*
    已知现在的位置了，但是当前这个位置不能杀人，因为这实际是个初始的位置，
    要寻找下一个杀人的位置
    那么第一步是找到一个活人，然后找到第interval个活人
  */
  int index_alive_person = 1 ;
  while(index_alive_person<=interval)
  {
    //sleep(10);
    //printf("%d ",index_alive_person);
    seek_one_alive_person(nums); //在这里面cur_pos的值会继续前进
    // printf("seek %dth person is cycle[%d] person,he is alive\n",index_alive_person,cur_pos);
    ++index_alive_person;
  }
  // if(cycle[cur_pos-1]==0)
  //printf("I am died\n");
  //else
  //printf("I am alive\n");
  if(cycle[cur_pos] == -1)
  {
    //杀了他
    //printf("kill cycle[%d]th person\n",cur_pos);
     cycle[cur_pos] = 0;
     // cur_pos=(cur_pos+1)%(2*nums);
     //display();
    return 0;
  }
  else
  {
    //printf("将杀一个好人cycle[%d]，interval= %d 是不好的\n",cur_pos,interval);
    return 1;
  }

}

void seek_one_alive_person(int nums)
{
  cur_pos = (cur_pos+1)%(2*nums);
  while(cycle[cur_pos]==0)
  {
    // printf("this man : %d died!\n",cur_pos+1);
    // sleep(3);
    cur_pos=(cur_pos+1)%(2*nums);
  }
}


int init_cycle(int len)
{
  int i = 0;
  while(i<=25)
  {
    if(i<= len-1)
      cycle[i] = 1;
    else if(i>=len&&i<=2*len-1)
      cycle[i] = -1;
    else
      cycle[i] = 0;
    ++i;
  }
  return 0;
}

void display()
{
  int i =0;
  while(i<=25)
    printf("%d ",cycle[i++]);
  printf("\n");
}