cf 496B Secret Combination

You got a box with a combination lock. The lock has a display showing n digits. There are two buttons on the box, each button changes digits on the display. You have quickly discovered that the first button adds 1 to all the digits (all digits 9 become digits 0), and the second button shifts all the digits on the display one position to the right (the last digit becomes the first one). For example, if the display is currently showing number 579, then if we push the first button, the display will show 680, and if after that we push the second button, the display will show 068.

You know that the lock will open if the display is showing the smallest possible number that can be obtained by pushing the buttons in some order. The leading zeros are ignored while comparing numbers. Now your task is to find the desired number.

题意：给出一个n位数和两种操作，操作1：给这个数的每个位上的数值加1（9会变成0），操作2：n位数右移一位（最后一位也就是个位上的数移到最高位）。现在要求运用这两种操作来使这个数最小化。

解法：因题目要求最小化这个数，对于操作1而言，要么让高位开始变为0（比如998923），要么让低位开始变为0（比如23789899），然后通过右移，此时才能使当前数更小化。所以我们可以先保存这个n位数所有右移后的数，然后对每个数保证最高位为0的情况下进行对这个数最小化，然后更新答案即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #define inf 0x7fffffff
 8 using namespace std;
 9 typedef long long ll;
10 const int maxn=1000+10;
11 int n;
12 char str[maxn][maxn];
13 char S[maxn];
14 int main()
15 {
16     while (scanf("%d",&n)!=EOF)
17     {
18         memset(S,0,sizeof(S));
19         scanf("%s",str[0]);
20         int len=strlen(str[0]);
21         for (int i=0 ;i<len ;i++) S[i]='9';
22         char s2[maxn];
23         memset(s2,0,sizeof(s2));
24 
25         strcpy(s2,str[0]);
26         int num=10-(s2[0]-'0');
27         for (int j=0 ;j<len ;j++)
28         {
29             int k=(s2[j]-'0'+num)%10;
30             s2[j]=k+'0';
31         }
32         if (strcmp(S,s2)>0) strcpy(S,s2);
33 
34         for (int i=1 ;i<n ;i++)
35         {
36             char c=str[i-1][0];
37             for (int j=1 ;j<len ;j++)
38             str[i][j-1]=str[i-1][j];
39             str[i][len-1]=c;
40             strcpy(s2,str[i]);
41             int num=10-(s2[0]-'0');
42             for (int j=0 ;j<len ;j++)
43             {
44                 int k=(s2[j]-'0'+num)%10;
45                 s2[j]=k+'0';
46             }
47             if (strcmp(S,s2)>0) strcpy(S,s2);
48         }
49         printf("%s
",S);
50     }
51     return 0;
52 }

View Code

后续：感谢提出宝贵的意见。。。