网易 2019 实习生编程题

网易 2019 实习生的编程题

• 牛牛找工作

每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
保证不存在两项工作的报酬相同。

示例：

3 3   
1 100 
10 1000 
1000000000 1001 
9 10 1000000000

输出：

100 
1000 
1001

思路：
用一个字典存储难度和对应的报酬，然后对输入的能力值与难度放在一起，意思就是能力值用不同的难度分开。
例如 [1, 9, 10, 10, 100, 100]，即能力 9 10 100 的能力在难度为 1 10 100 中的位置，可以清楚地看到 9 是小于 难度 10 的，所以 9 的报酬只能为难度 1 对应的报酬。

from collections import defaultdict
# 获取工作数量 朋友数量
jobs, frineds_nu = list(map(int, raw_input().split()))
i, dp = 0, []
while i < jobs:
    # 获取工作对应难度和报仇，将其打包为一个列表后存入列表 dp
    v = list(map(int, raw_input().split()))
    if len(v) == 2:
        dp.append(v)
        i += 1
frineds_ability = []
while len(frineds_ability) != frineds_nu:
    # 获取朋友的能力
    frineds_ability = list(map(int, raw_input().split()))

# 构造一个字典来存储难度和对应的报酬
dp = defaultdict(int, dp)
# defaultdict 不存在的键默认值是 0
max_ = 0
# 将朋友能力与工作难度进行排序，后面确定报酬
abilities = sorted(list(dp.keys()) + frineds_ability)

for i in abilities:
    # 遍历难度，确定能力对应的报酬的最大值，将那些能力大于难度的 能力:报酬 存入 dp
    max_= max(dp[i], max_)
    dp[i] = max_
for i in frineds_ability:
    print(dp[i])

说实话，用 python 处理输入的情况我用的不是很多，感觉很不舒服，有没有一种比较友好的输入方法。

• 被 3 整除

小Q得到一个神奇的数列: 1, 12, 123,...12345678910,1234567891011...。
并且小Q对于能否被3整除这个性质很感兴趣。

小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。
思路：
这是个找规律题

1  2  3   4     5     6      7
1 12 123 1234 12345 123456 1234567
1, 4, 7 不能被 3 整除
由此发现规律，3n + 1 (n>=0) 都不能被 3 整除

也不知道这么算对不对。。。

l, r = map(int, raw_input().split())
count = 0
for i in range(l, r+1):
    if i%3 != 1:
        count += 1
print count

待更。。。