ACM刷题之路（十五）分治法 + 找规律 ZOJ4085

男娘i 2024-02-19 18:11 55阅读 0赞

**题目链接**：[http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5864][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;
    }

[http_acm.zju.edu.cn_onlinejudge_showProblem.do_problemId_5864]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5864