第K人||约瑟夫环（链表）

http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4442

很容易超时

通过数组来记录，删除

//数组从1开始好像不行后面一些数字就乱码了，因为此时now的值使得坐标可能为0，一些情况下，a【0】成功上位，一些却不行。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 int main()
 8 {
 9     int t,n,a[1005];
10     int k;
11     scanf("%d",&t);
12     while(t--)
13     {
14         scanf("%d%d",&n,&k);
15         for(int i=0;i<n;i++)
16             a[i]=i;
17         int now=0;
18         while(n>1)
19         {
20            now+=k-1;
21            now%=n;
22            for(int i=now;i<n-1;i++)
23             a[i]=a[i+1];
24            n--;
25         }
26        printf("%d
",a[0]+1);
27 
28     }
29     return 0;
30 }

View Code

http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=5016&pid=4

题意差不多，但是用链表来写//两题数据不一样，用链表解上题会超时

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<stdlib.h>
 8 #define mem(a) memset(a,0,sizeof(a))
 9 const double pi=acos(-1.0);
10 using namespace std;
11 typedef struct node{  //C++中用typedef定义 则下面的p当struct node用
12 int num;
13 struct node*next;
14 }p;
15 p*link(int n)
16 {
17     p*head=(p*)malloc(sizeof(p));
18     head->num=1;
19     head->next=NULL;
20     p*c=head;
21     for(int i=2;i<=n;i++)
22     {
23         p*body=(p*)malloc(sizeof(p));
24         body->num=i;
25         body->next=NULL;
26         c->next=body;
27         c=c->next;
28     }
29     c->next=head; //首尾相连
30     return head;
31 }
32 void f(p*head,int k,int m)
33 {
34     p*tail=head;
35     while(tail->next!=head)
36         tail=tail->next; //尾结点,作删除用
37     p*pp=head;
38     while(pp->num!=k)
39     {
40         tail=pp;
41         pp=pp->next;
42     }
43     while(pp->next!=pp)
44     {
45         for(int i=1;i<m;i++)
46         {
47             tail=pp;
48             pp=pp->next;
49         }
50         tail->next=pp->next;
51         free(pp);
52         pp=tail->next;
53     }
54     printf("%d
",pp->num);
55 }
56 int main()
57 {
58   int t,n,m;
59   cin>>t;
60   while(t--)
61   {
62       scanf("%d%d",&n,&m);
63       p*head=link(n);
64       f(head,1,m);
65   }
66   return 0;
67 }

View Code