题解：P1145 约瑟夫

XiaoYang_awa · 2025-01-06 18:17:10 · 题解

P1145 约瑟夫

题意已经明确，不过多阐述。

【前置知识：链表】

我们发现嘎人的操作类似链表的删除节点，所以这道题我们可以用枚举+链表来做。

思路：

• 首先是框架和链表结构体的创建，data用来记录是好人还是坏人。

  #include<bits/stdc++.h>
  using namespace std;
  struct Node{
  bool data;
  Node *next;
  };
  int main(){
  }

• 我们从 k+1 开始枚举 m，能节约时间。为了不超时我们还可以在特判一下。

  for(int m=k+1;;m++){//外层循环
  if(m%(k+k)<=k&&m%(k+k)!=0)continue;//一定会嘎到好人的情况
  }

• 对于每一次枚举，都要先初始化。

  Node *head=new Node,*tail=head;//创建头和尾
  head->data=1;//标记头一定是好人
  for(int i=2;i<=k+k;i++){//for循环生成链表
  Node *n=new Node;
  n->data=(i<=k),n->next=nullptr,tail->next=n,tail=n;//加入节点，更新尾
  }
  tail->next=head,tail=head;//完成一个循环链表

• 判断此方案是否可行。

  int cnt=0;//用计数变量存储嘎了多少坏人
  for(int i=1;i<=k;i++){
  for(int j=1;j<=(m-2)%(k+k-cnt);j++)tail=tail->next;//报数操作
  if(tail->next->data)break;//嘎到好人就要break
  tail->next=tail->next->next,tail=tail->next,cnt++;
  }
  if(cnt==k){cout<<m;return 0;}//如果已经找到就输出

• 为了不炸内存，每次枚举完后要将这一个链表释放掉空间。

  tail=head;
  while(tail->next!=head){Node *temp=tail;tail=tail->next;delete temp;}
  delete tail;

  完整代码：

  拒绝抄题解，从你我做起
  #include<bits/stdc++.h>
  using namespace std;
  struct Node{
  bool data;
  Node *next;
  };
  int main(){
  int k;
  cin>>k;
  for(int m=k+1;;m++){
      if(m%(k+k)<=k&&m%(k+k)!=0)continue;
      Node *head=new Node,*tail=head;
      head->data=1;
      for(int i=2;i<=k+k;i++){
          Node *n=new Node;
          n->data=(i<=k),n->next=nullptr,tail->next=n,tail=n;
      }
      tail->next=head,tail=head;
      int cnt=0;
      for(int i=1;i<=k;i++){
          for(int j=1;j<=(m-2)%(k+k-cnt);j++)tail=tail->next;
          if(tail->next->data)break;
          tail->next=tail->next->next,tail=tail->next,cnt++;
      }
      if(cnt==k){cout<<m;return 0;}
      tail=head;
      while(tail->next!=head){Node *temp=tail;tail=tail->next;delete temp;}
      delete tail;
  }
  } 

完结撒花！