HDU 4611 Balls Rearrangement 解题报告

题意：球的编号为 0 - N-1 最开收有 A 个老箱子，编号为 1 - A-1 把球的编号%A 就是球所放的箱子数，现在新购入 B 个新箱子，，把所有的老箱子中的按照原来的规则（%B）放入新箱子中，移动的距离（|老箱子编号-新箱子编号|）为花费，求总花费

解题思路: 把n分为较大的一段一段（根据循环节）因为N 较大,所以对这些编号求一个循环节，每个循环节中的状态一样，然后对每个循环节里面的小段分情况讨论！

解题代码：

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <math.h>
  4 long long gcd(long long a, long long b)
  5 {
  6     return b == 0 ? a:gcd(b,a%b);
  7 }
  8 long long ABS( long long a)
  9 {
 10   if(a <= 0 )
 11       return -a ; 
 12   else 
 13       return a;
 14 }
 15 int main()
 16 {
 17     //freopen("1001.in","r",stdin);
 18     long long t ;
 19     scanf("%I64d",&t);
 20     while(t--)
 21     {
 22         long long k , n , m ;
 23         scanf("%I64d %I64d %I64d",&k,&n,&m);
 24         // printf("%I64d %I64d
",n,m);
 25         if(m < n )
 26         {
 27             long long temp = n;
 28             n = m;
 29             m = temp ;
 30         }
 31 
 32         long long step = n* m /gcd(n,m);
 33         long long sum = 0 ;
 34         long long t = 1;
 35         // printf("%I64d**
",step);
 36         k = k - 1 ; 
 37         // printf("%I64d %I64d %I64d
",k,step,gcd(3,4));
 38         if(k >= step )
 39         {
 40 
 41             for(long long i = 1; i <= step/n -1; i ++)
 42             {
 43                 if((i+1) * n - 1 >= t *m )
 44                 {
 45 
 46                     sum += ((i*n) % m) *(t*m - i *n);
 47                     sum += (((i+1)*n-1) - t * m +1) *(ABS(((i + 1 )*n -1)%m - (n-1)));
 48                     t ++ ;
 49                     // printf("
******%I64d
",(i*n) % m);
 50                 }
 51                 else
 52                 {
 53                     sum += ((i*n) % m ) * n;
 54                     // printf("
******%I64d
",(i*n % m));
 55                 }
 56 
 57             }
 58             // printf("
******%I64d
",sum);
 59             sum *= (k/step);
 60             k = k - (step)*(k/step);
 61         }
 62 
 63         t = 1;
 64         for(long long i = 0; ; i ++ )
 65         {
 66             if(k >= (i+1) * n )
 67             {
 68                 if((i+1) * n - 1 >= t *m )
 69                 {
 70 
 71                     sum += ((i*n) % m) *(t*m - i *n);
 72                     //printf("%I64d
",sum);
 73                     sum += (((i+1)*n-1) - t * m + 1) *(ABS(((i + 1 )*n -1)%m - (n-1)));
 74                     t ++ ;
 75                 }
 76                 else
 77                 {
 78                     sum += ((i*n) % m ) * n;
 79                 }
 80                 // printf("
1*****%I64d
",sum);
 81             }
 82             else
 83             {
 84                 if(t * m <= k )
 85                 {
 86                     sum += ((i*n) % m) *(t*m - i *n);
 87                     // printf("%I64d
",sum);
 88                     sum += (k - t*m + 1 ) *(ABS(((i + 1 )*n -1)%m - (n-1)));
 89                     t++;
 90                 }
 91                 else
 92                     sum +=(i*n % m ) * (k - i*n +1);
 93                 //printf("
2*****%I64d
",sum);
 94                 break;
 95             }
 96         }
 97 
 98         printf("%I64d
",sum);
 99 
100     }
101     return 0 ;
102 }

View Code

没有梦想，何谈远方