ACM刷题之路（十五） 分治法 + 找规律 ZOJ4085
题目链接：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变量是中间储蓄某长度的数字满足的个数
ll f(ll x)//求数值小于x且字典序也小于x的数字个数{int cnt = go(x);if (cnt == 1){return x - p[cnt - 1] - 1;}ll sum_ = x - p[cnt - 1];for (int i = 1; i < cnt; i++){ll sum = x / p[i];if (i == cnt - 1){sum_ += sum - p[cnt - i - 1];}else{sum_ += sum - p[cnt - i - 1] + 1;}}return sum_;}
第二块：
求 比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
代码：
ll ff(ll x, int m)//需要m个数字 比x小 x = 2 m = 4{int cnt = go(x);//x的位数 cnt = 1ll sum = x; // sum = 20ll sum_ = 0;//已经找到sum_个数字 sum- = 0for (int i = cnt;; i++) //i=1{sum = sum * 10; // sum = 20sum_ = sum - p[i]; // 10到19if (sum_ <= m)//当前位最大填充的数字个数 小于 m个数字{m -= sum_;//需要填充的数字 减去 当前位最大填充的数字个数}else//如果超过了{return p[i] + m - 1; // 10 + 2 - 1}}}
总的代码：
#include <iostream>using namespace std;#define ll long longll p[18];void init(){p[0] = 0;p[1] = 10;for (int i = 2; i <= 17; i++){p[i] = p[i - 1] * 10;}}int go(int x){int cnt = 0;while (x){x /= 10;cnt++;}return cnt;}ll f(ll x)//求数值小于x且字典序也小于x的数字个数{int cnt = go(x);if (cnt == 1){return x - p[cnt - 1] - 1;}ll sum_ = x - p[cnt - 1];for (int i = 1; i < cnt; i++){ll sum = x / p[i];if (i == cnt - 1){sum_ += sum - p[cnt - i - 1];}else{sum_ += sum - p[cnt - i - 1] + 1;}}return sum_;}ll ff(ll x, int m)//需要m个数字 比x小 x = 2 m = 4{int cnt = go(x);//x的位数 cnt = 1ll sum = x; // sum = 20ll sum_ = 0;//已经找到sum_个数字 sum- = 0for (int i = cnt;; i++) //i=1{sum = sum * 10; // sum = 20sum_ = sum - p[i]; // 10到19if (sum_ <= m)//当前位最大填充的数字个数 小于 m个数字{m -= sum_;//需要填充的数字 减去 当前位最大填充的数字个数}else//如果超过了{return p[i] + m - 1; // 10 + 2 - 1}}}int main(){init();int T;cin >> T;while (T--){ll k, m;scanf("%lld%lld", &k, &m);m = m - f(k) - 1;if (m < 0)//不符合条件{cout << 0 << endl;continue;}if (m == 0) // 正好跟普通排序一样{cout << k << endl;continue;}cout << ff(k, m) << endl;}return 0;}
àì夳堔傛蜴生んèń
╰+攻爆jí腚メ
男娘i
不念不忘少年蓝@
还没有评论，来说两句吧...