SGU193 Chinese Girls' Amusement（数论，约瑟夫环问题）

题意：给定n个人，围成一圈，求一个最大的K（1 <= k <= n/2），使得从第一个人开始，向左数k个人，每个人都能数到，最后回到第一个人

解题思路：其实是求<= n/2 的且与n互质的最大的数，根据性质，我们知道，如果是n是奇数，答案就是n/2，如果是偶数，就是小于n/2的最大的奇数（当然要用到高精度。。）

解题代码：

  1 // File Name: g.c
  2 // Author: darkdream
  3 // Created Time: 2013年09月03日 星期二 16时02分52秒
  4 
  5 #include<stdio.h>
  6 #include<string.h>
  7 #include<stdlib.h>
  8 #include<time.h>
  9 #include<math.h>
 10 #include<ctype.h>
 11 #define maxn  100005 
 12 struct node2{
 13   int x, y,num;
 14 }first[maxn],stack[maxn];
 15 int pre[maxn];
 16 int cmp1(const void * a,const void *b)
 17 {
 18    if((*(node2*)a).x == (*(node2*)b).x)
 19    {
 20       return (*(node2*)b).y - (*(node2*)a).y;
 21    }
 22    else return (*(node2*)a).x - (*(node2*)b).x;
 23 }
 24 void print(int x)
 25 {
 26   while(1)
 27   {
 28     printf("%d ",x);
 29     if(pre[x] == 0 )
 30     {    
 31         return ;
 32     }
 33     x = pre[x];
 34     printf("%d ",x);
 35   }
 36     
 37 }
 38 int find(int flor,int y)
 39 {
 40    int l = 1; 
 41    int r = flor;
 42    while(l <= r)
 43    {
 44       int mid = (l+r)/2;
 45       if(stack[mid].y < y )
 46           if(stack[mid].y >= y)
 47               return mid + 1; 
 48           else 
 49               l = mid  +1;
 50       else 
 51           r = mid - 1;
 52    }
 53    return l;
 54 }
 55 void slove(int n)
 56 {
 57    memset(pre,0,sizeof(pre));
 58    stack[0].y = 0 ;
 59    stack[0].x = 0 ;
 60    stack[0].num = 0;
 61    int flor = 0 ;
 62    for(int  i = 1;i <= n ;i ++)
 63    {
 64       if(first[i].y > stack[flor].y)
 65       {
 66          flor++;
 67          stack[flor].y = first[i].y;
 68          stack[flor].num = first[i].num;
 69          stack[flor].x = first[i].x;
 70          pre[first[i].num] = stack[flor-1].num;   
 71       }
 72       else {
 73         int low = find(flor,first[i].y);
 74         stack[low].y = first[i].y ; 
 75         stack[low].num = first[i].num;
 76         stack[low].x = first[i].x;
 77         pre[first[i].num] = stack[low-1].num;
 78       }
 79 
 80    }
 81    printf("%d
",flor);
 82    print(stack[flor].num);
 83    printf("
");   
 84    
 85 }
 86 
 87 int main(){
 88 
 89    //freopen("/home/plac/problem/input.txt","r",stdin);
 90    //freopen("/home/plac/problem/output.txt","w",stdout);
 91    int n;
 92    while(scanf("%d
",&n) != EOF)
 93    {
 94        for(int i = 1;i <= n;i ++)
 95       { 
 96         scanf("%d %d",&first[i].x,&first[i].y);
 97         first[i].num = i ; 
 98       }
 99       qsort(first+1,n,sizeof(node2),cmp1);
100       slove(n);
101    }
102 return 0 ;
103 }

View Code

没有梦想，何谈远方