Codeforces 758D 392-Div.2 Ability To Convert

题目链接:Ability To Convert

题意:

输入有两行,第一行的数字表示K进进制,例如16表示16进制,2 <= K <= 10^9。第二行是一个字符串S,由纯数字组成,你可以将这个字符串进行分割,对应为K进制每一位。例如K=16,S=”11311”,可以将S分割为”1”, “13”, “11”,则对应为 1*16^2 + 13*16^1 + 11*16^0;也可以分割为”11”, “13”, “11”;但不能分割为”113”, “11”,因为”113”已经超过16,不能用来表示16进制。

怎么分割S,使得这个K进制数转化为10进制时最小,例如上面的S,分割为”1”, “13”, “11”,475 = 1*16^2 + 13*16^1 + 11*16^0,转化为10进制数为475,是最小的。输出最小的10进制结果。

题解:

贪心。

贪心规则:从低位开始读取,尽可能读取最多的数字,最后就能保证得到的数字最小。
例如K=200,S=”1234567”, 首先尽可能读取出来的一块是”67”,然后是”45”,最后是”123”,对应的10进制数就是123*200^2 + 45*200^1, 67*200^0

证明:

  1. 问题等价于,怎么切分S最合适,切出的份数越少越优,因为份数多了,对应的K进制的指数就越大,结果一定更大
  2. 在切出的份数相同的情况下,要先满足高位的数字尽可能的小。例如K=16,S=”11311”;”1”,”13”, “11”切成3份; “11”, “3”, “11”切成3份,但第一种切法更优,因为最高位的”1”比”11”小。
  3. 将S字符串看出字符序列[s1, s2, s3 …. sn],从末尾开始贪心读取,最多可以读取到sk,则序列分成两份:[s1, s2, s3 … sk-1], [sk, sk+1, sk+2 … sn]。假设不是贪心读取,将sk归在第一个序列,则第一个序列为[s1, s2, s3 …. sk-1, sk]

    对比这两个序列:
    A: [s1, s2, s3 ... sk-1]
    B: [s2, s2, s3 ... sk-1, sk]

    假设A序列采用了最优划分的方法,保证结果最优。

    B序列比A序列多一个字符sk,有以下情况:
    a. sk独立分一块,则等价于A的划分里面,追加一个sk,导致总块数增加,结果必定更大。
    b. sk和sk-1归在同一块,按照A序列的最优划分方法来划分,则总块数不变,但最后一块的值变大了,结果更大。
    c. sk和sk-1归在同一块,使用其他划分方法。假设新的划分结果比A序列的划分更优,则A序列必定可以采用这种划分方法,使得A的划分结果比原来更优。但已经假设A序列是最优划分方法,所以矛盾,不会存在一种划分方法使得B优于A

    综上,B序列无论怎么划分都不可能比A的最后划分方法更优,所以sk不能与A序列共同参与划分。因此,每轮读取时都要贪心读取,则最后结果最优。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
base = int(raw_input().strip())
bits = raw_input().strip()
bitlen = len(bits)
stack = []

def comp(a, b):
if b - a + 1 > len(str(base)):
return False
return int(bits[a:b+1]) < base

l = r = bitlen-1
while r >= 0:
ll = l
while ll >= 0:
if bits[ll] != '0':
res = comp(ll, r)
if res: l = ll
else: break
ll -= 1

stack.append(int(bits[l:r+1]))
l = r = l - 1

#print stack[::-1]
ans = 0
for i, a in enumerate(stack):
ans += a * (base ** i)
print ans
坚持原创分享,您的支持将鼓励我继续创作!