ACM刷题之路（十五） 分治法 + 找规律 ZOJ4085
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 = 1
ll sum = x; // sum = 20
ll sum_ = 0;//已经找到sum_个数字 sum- = 0
for (int i = cnt;; i++) //i=1
{
sum = sum * 10; // sum = 20
sum_ = sum - p[i]; // 10到19
if (sum_ <= m)//当前位最大填充的数字个数 小于 m个数字
{
m -= sum_;//需要填充的数字 减去 当前位最大填充的数字个数
}
else//如果超过了
{
return p[i] + m - 1; // 10 + 2 - 1
}
}
}总的代码：
#include <iostream>
using namespace std;
#define ll long long
ll 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 = 1
ll sum = x; // sum = 20
ll sum_ = 0;//已经找到sum_个数字 sum- = 0
for (int i = cnt;; i++) //i=1
{
sum = sum * 10; // sum = 20
sum_ = sum - p[i]; // 10到19
if (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;
}腾讯云开发者
