网易 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
待更。。。
