题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5864
题意：
已知K 和 M，满足K在1~N的字典序排列中，处于第M位，求N的最小值。
比如K =2 ，M = 4 的情况，N的最小值为11；
1到11
按照数值排列： 1 2 3 4 5 6 7 8 9 10 11
按照字典序排列： 1 10 11 2 3 4 5 6 7 8 9
2在字典序排列中处于第4位，符合条件，所以N=11就是答案。
题解：
任何一个数X在字典序的排列中的位置，与比X字典序小的个数一一对应。
举个例子：在1~11的排列中，字典序比2小的数字有3个，所以2的位置是3 + 1 = 4.这个相信不难理解。
其实这个问题属于NP问题，验证比较简单，但是求答案比较麻烦，我在这采用的是分治法。
首先，比X字典序小的数字分为两类：
1.比X字典序小 && 数值比X小
2.比X字典序小 && 数值比X大
那么我们把两个都求出来，答案不就出来了吗？
第一块：求 比X字典序小 && 数值比X小 的数字个数
例1： 18
- 10~17 共8个
- 1 共1个
总计9个
例2： 118
- 100~117 共18个
- 10~11 共2个
- 1 共1个
总计21个
例3： 1234
- 1000~1233 共234个 A
- 100~123 共24个 B
- 10~12 共3个 C
- 1 共1个 D
一共262个
发现规律了吗？
以1234为例
A：1234/1=1234 ； 1234-1000=234个；
B：1234/10=123 ； 123-100+1=24个；
C：1234/100=12； 12-10+1 = 3个；
D ：1234/1000=1 ； 1-1+1 = 1个；
用代码实现：go函数取X的位数 如 88 两位 999 三位
p数组是10的i次方(除0) p[0]=0 p[1]= 10 p[2] = 100......
sum_ 变量统计计算满足的个数
sum变量是中间储蓄某长度的数字满足的个数
1. ll f(ll x)//求数值小于x且字典序也小于x的数字个数 2. { 3. int cnt = go(x); 4. if (cnt == 1) 5. { 6. return x - p[cnt - 1] - 1; 7. } 8. ll sum_ = x - p[cnt - 1]; 9. for (int i = 1; i < cnt; i++) 10. { 11. ll sum = x / p[i]; 12. if (i == cnt - 1) 13. { 14. sum_ += sum - p[cnt - i - 1]; 15. } 16. else 17. { 18. sum_ += sum - p[cnt - i - 1] + 1; 19. } 20. } 21. return sum_; 22. }
第二块：
求 比X字典序小 && 数值比X大 的数字个数
M 是数字 K 在1~N 排列的序号 前面求的 （比X字典序小 && 数值比X小 的数字） 一定在K的前面
这点毋容置疑，我们设满足比X字典序小 && 数值比X小 的数字的个数为 X
情况1.
若 X + 1 ==M 则答案=K
比如6 在1~N的排名为6 那K就是自己本身（6）了
情况2：
若X + 1 > M 则答案 = 0，因为不满足条件 比如
数字1 求排名第6的情况 ，是不存在的
情况3：
我们需要补M - X - 1 个数进去 ， 使满足条件 。
例1:
K = 2 M = 4
第一块求得f(K) = 1；即比X字典序小 && 数值比X小个数为1 就是1
M必须先减去这个1 再减去本身的1 就是需要填补的数量
M - 1 - 1 = 2；
我们先把K乘10 ； 2 * 10 = 20；
再减去10 ； 20 - 10 = 10 ；这个10 就是两位的时候最多可以填补的数字量 即10~19；
如果不够 m减去这个量，继续遍历三位的情况
比如此例 ，够了 就return 10 + 2 - 1 = 11 ，则11就是答案。
同理：例2：
K = 3 M = 14
M = 14 - 2 - 1 = 11个；
3 * 10 = 30；
30 - 10 = 20；
最多填补的20个，大于需要的M(11个) 所以return 10 + 11 - 1 = 20，则20 就是答案
最后 例3：
K = 3 M = 34
M = 34 - 2 - 1 = 31个；
3 * 10 = 30 ；
30 - 10 = 20；
20 < 31 不够 所以 m - =20 ----> m = 11 个 还需要填充11个
30 * 10 = 300；
300 - 100 = 200个 即三位数的情况最多可以填充200个
此时 200 > 11 够了 就 return 100 + 11 - 1 = 110 答案就是110
代码：
1. ll ff(ll x, int m)//需要m个数字 比x小 x = 2 m = 4 2. { 3. int cnt = go(x);//x的位数 cnt = 1 4. ll sum = x; // sum = 20 5. ll sum_ = 0;//已经找到sum_个数字 sum- = 0 6. for (int i = cnt;; i++) //i=1 7. { 8. sum = sum * 10; // sum = 20 9. sum_ = sum - p[i]; // 10到19 10. if (sum_ <= m)//当前位最大填充的数字个数 小于 m个数字 11. { 12. m -= sum_;//需要填充的数字 减去 当前位最大填充的数字个数 13. } 14. else//如果超过了 15. { 16. return p[i] + m - 1; // 10 + 2 - 1 17. } 18. } 19. }
总的代码：
1. #include <iostream> 2. using namespace std; 3. #define ll long long 4. ll p[18]; 5. void init() 6. { 7. p[0] = 0; 8. p[1] = 10; 9. for (int i = 2; i <= 17; i++) 10. { 11. p[i] = p[i - 1] * 10; 12. } 13. } 14. int go(int x) 15. { 16. int cnt = 0; 17. while (x) 18. { 19. x /= 10; 20. cnt++; 21. } 22. return cnt; 23. } 24. ll f(ll x)//求数值小于x且字典序也小于x的数字个数 25. { 26. int cnt = go(x); 27. if (cnt == 1) 28. { 29. return x - p[cnt - 1] - 1; 30. } 31. ll sum_ = x - p[cnt - 1]; 32. for (int i = 1; i < cnt; i++) 33. { 34. ll sum = x / p[i]; 35. if (i == cnt - 1) 36. { 37. sum_ += sum - p[cnt - i - 1]; 38. } 39. else 40. { 41. sum_ += sum - p[cnt - i - 1] + 1; 42. } 43. } 44. return sum_; 45. } 46. ll ff(ll x, int m)//需要m个数字 比x小 x = 2 m = 4 47. { 48. int cnt = go(x);//x的位数 cnt = 1 49. ll sum = x; // sum = 20 50. ll sum_ = 0;//已经找到sum_个数字 sum- = 0 51. for (int i = cnt;; i++) //i=1 52. { 53. sum = sum * 10; // sum = 20 54. sum_ = sum - p[i]; // 10到19 55. if (sum_ <= m)//当前位最大填充的数字个数 小于 m个数字 56. { 57. m -= sum_;//需要填充的数字 减去 当前位最大填充的数字个数 58. } 59. else//如果超过了 60. { 61. return p[i] + m - 1; // 10 + 2 - 1 62. } 63. } 64. } 65. int main() 66. { 67. init(); 68. int T; 69. cin >> T; 70. while (T--) 71. { 72. ll k, m; 73. scanf("%lld%lld", &k, &m); 74. m = m - f(k) - 1; 75. if (m < 0)//不符合条件 76. { 77. cout << 0 << endl; 78. continue; 79. } 80. if (m == 0) // 正好跟普通排序一样 81. { 82. cout << k << endl; 83. continue; 84. } 85. cout << ff(k, m) << endl; 86. } 87. return 0; 88. }
