首页 > 试题广场 >

头条校招

[编程题]头条校招
  • 热度指数：17815 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
头条的2017校招开始了！为了这次校招，我们组织了一个规模宏大的出题团队，每个出题人都出了一些有趣的题目，而我们现在想把这些题目组合成若干场考试出来，在选题之前，我们对题目进行了盲审，并定出了每道题的难度系统。一场考试包含3道开放性题目，假设他们的难度从小到大分别为a,b,c，我们希望这3道题能满足下列条件：
a<=b<=c
b-a<=10
c-b<=10
所有出题人一共出了n道开放性题目。现在我们想把这n道题分布到若干场考试中（1场或多场，每道题都必须使用且只能用一次），然而由于上述条件的限制，可能有一些考试没法凑够3道题，因此出题人就需要多出一些适当难度的题目来让每场考试都达到要求，然而我们出题已经出得很累了，你能计算出我们最少还需要再出几道题吗？

输入描述:
输入的第一行包含一个整数n，表示目前已经出好的题目数量。

第二行给出每道题目的难度系数d1,d2,...,dn。 

数据范围

对于30%的数据，1 ≤ n,di ≤ 5;

对于100%的数据，1 ≤ n ≤ 10^5,1 ≤ di ≤ 100。

在样例中，一种可行的方案是添加2个难度分别为20和50的题目，这样可以组合成两场考试：（20 20 23）和（35,40,50）。


输出描述:
输出只包括一行，即所求的答案。
示例1

输入

4  
20 35 23 40

输出

2
算法知识视频讲解
添加回答
Python
fengqh头像 fengqh 
n = input()
d = [int(x) for x in input().split()]
d.sort()
previous = 0
sum = 0
per = 1
while len(d):
    if per == 1:
        previous = d.pop(0)
        per += 1
    elif per == 2:
        if d[0] - previous > 10 :
            previous += 10
            sum += 1
            per += 1
        else:
            previous = d.pop(0)
            per += 1
    elif per ==3:
        if d[0] - previous > 10 :
            previous += 10
            sum += 1
            per = 1
        else:
            previous = d.pop(0)
            per = 1
if per != 1:
    sum += 4 - per 
print(sum)
很复杂，多个变量记录历史值，比如（1,89,90）这种用previous记录前面一个值，用per记录是否三个一组。
sum计算需要插入的值。按照最大间隔10插入。

发表于 2021-03-12 12:03:21 回复(0)
Python
酒鬼考拉头像 酒鬼考拉
Python 找到规律显而易见的简单
先将列表升序
遍历列表，判断 dn[i] - dn[i-1] 的区间
如果在10-20 ：总数加1
如果大于20：总数加2
遍历完后用总数(count+n)%3来判断是不是3的余数，再用count加到是3的余数，输出结果就可以了 
n = int(input())
dn = [int(x) for x in input().split()]
dn.sort()
count = 0
for i in range(1,len(dn)):
    if 10 < dn[i] - dn[i-1] <= 20:
        count += 1
    if dn[i] - dn[i-1] > 20:
        count += 2
if (count+n)%3:
    count += (3 - (count+n)%3)
print(count)


发表于 2020-09-19 06:54:30 回复(0)
Python
开始-蒙了头像 开始-蒙了
使用min heap做的 

	importsys





	importheapq





	defget_inputs():





	    try:





	        line =sys.stdin.readlines()





	        num, difficulties =int(line[0].strip()), line[1].strip().split(' ')





	        difficulties =map(int, difficulties)





	        difficulties =[int(d) ford indifficulties]





	        returnnum, difficulties





	    except:





	        returnNone, None





	 





	     





	defget_min_extra_num(num, difficulties):





	    heapq.heapify(difficulties)





	    comb =[]





	    res =0





	    whiledifficulties:





	        n =heapq.heappop(difficulties)





	        ifnotcomb:





	            comb.append(n)





	        elifn > comb[-1] +20:





	            res +=(3-len(comb))





	            heapq.heappush(difficulties, n)





	            comb =[]





	        elifn > comb[-1] +10:





	            iflen(comb) ==2:





	                heapq.heappush(difficulties, n)





	            res +=1





	            comb =[]





	        else:





	            comb.append(n)





	            iflen(comb) ==3:





	                comb =[]





	             





	    ifcomb:





	        res +=(3-len(comb))





	    returnres





	 





	num, diff =get_inputs()


print(get_min_extra_num(num, diff))

发表于 2019-03-15 07:10:06 回复(0)
Python
tjjsjwhj头像 tjjsjwhj 
# 按难度系数排序
# 如果相邻的两个难度系数差距大于10，分段
# 每一段长度%3，过滤出余数为1和2的
# 余数是2的情况下，有几段，就添加几个数
# 余数为1情况下，看相邻两段，能插入的，加一，然后跳过一段，不能的加二

while True:
    try:
        n = int(input())
        hard_index = list(map(int, input().split()))
        hard_index = sorted(hard_index)
        note = []
        temp = []
        for i in range(n-1):
            if hard_index[i]+10<hard_index[i+1]:
                temp.append(hard_index[i])
                note.append(tuple(temp))
                temp = []
                continue
            temp.append(hard_index[i])
        temp.append(hard_index[-1])
        note.append(tuple(temp))
        note1 = list(filter(lambda x:len(x)%3==1, note))
        note2 = list(filter(lambda x:len(x)%3==2, note))
        count = 0
        count += len(note2)
        flag = 0
        for i in range(len(note1)-1):
            if flag:
                flag = 0
                continue
            if note[i][-1]+20>=note[i+1][0]:
                count += 1
                flag = 1
            else:
                count += 2
        if not flag and len(note1):
            count += 2
        print(count)
    except:
        break

编辑于 2018-07-26 17:19:50 回复(0)
Python
星缘小梦头像 星缘小梦
import sys
n=int(raw_input())
data= map(int, sys.stdin.readline().split())
data.sort()
i=0
num=0
while(i<=n-3):
    if data[i+1]-data[i]<=10:
        if data[i+2]-data[i+1]<=10:
            i=i+3
            continue
        else:
            i+=2
            num+=1
    else:
        if data[i+1]-data[i]<=20:
            i+=2
            num+=1
        else:
            i+=1
            num+=2
if (n-i)==1:
    num= num+2
if (n-i)==2:
    if data[i+1]-data[i]<=20:
        num+=1
    else:
        num+=4
        
print num

发表于 2018-07-06 10:21:01 回复(0)
Python
离疏头像 离疏 
n=int(input())
p,count=1,0
d=sorted(list(map(int,input().split())))
for i in range(1,n):
    if p<3:#P为每场考试中已有题目数量
        if d[i]-d[i-1]<=10:#相邻题目难度差距在10以内，则该场考试题目数量加1
            p+=1
        elif p==1 and d[i]-d[i-1]<=20:#若相邻两题目的难度差距在20之内，且已有一道题目，则在中间插入一道
            count+=1
            p=3
        else:#相邻两题目难度差距大于20，或难度在20以内但已有题目超过1，则该场考试还需3-p道题
            count+=3-p
            p=1
    else:
        p=1
count+=3-p#补上最后一场考试所缺的题目数
print(count)

发表于 2018-06-30 22:18:46 回复(0)
Python
crazyhoney头像 crazyhoney
看了fengcq的解题思想，我也用动态规划尝试了一下：
dp[i] 即为前i+1个题目最少应该插入多少道题目。（i从0开始）
初始值dp[0]=2.因为开始什么都不知道，一进来看到一道题目，当然要给他添加2道题目才符合要求。
转移方程：
dp[i] =  2                if dp[i-1]=0
dp[i-1]+2   if dp[i]-d[i-1]>20
dp[i-1]-1   if dp[i]-d[i-1]<=20
如此转移，dp[n-1]即为答案 
import sys
 
n = int(raw_input())
d = map(int, sys.stdin.readline().split())
d.sort()
dp = [0]*n
dp[0] = 2
for i in range(1,len(d)):
    if dp[i-1] == 0:
        dp[i] = 2
        continue
    if d[i]-d[i-1] >20:
        dp[i] = dp[i-1] + 2
    else:
        dp[i] = dp[i-1] -1
print dp[n-1]


编辑于 2017-08-22 12:26:31 回复(2)
Python
呱呱许头像 呱呱许
''' 
说不上很难，但是边界条件一定要想好，也算不上动态规划问题，只要排序好即可。题目漏洞之一就是，并没有对考场数量做限制。升级版本可能1.有此限制，2.要求打印出满足条件的其中一种难题组合，3.添加几道难题+每题难题系数【窝草，感觉这个就真的很动态很难了】
'''
import sys

total = int(sys.stdin.readline().strip())
difficult = map(int,sys.stdin.readline().strip().split())
difficult.sort()

def addnum(N,dlist):
    i = 0;ret = 0
    while i < (N-2):
        if dlist[i]+10>=dlist[i+1]:
            if dlist[i+1]+10 >= dlist[i+2]:
                i += 3
            else:
                ret += 1
                i += 2
        else:
            ret += 2
            i += 1
        if i == N-2:
            if (dlist[-2]+10>=dlist[-1]):
                ret += 1
            else:
                ret += 4
        if i == N-1:
            ret += 2
    return ret
    
print(addnum(total,difficult))
发表于 2017-08-22 02:33:30 回复(0)
提交观点

问题信息

贪心
来自：字节跳动2017秋招开...
难度：
9条回答 22709浏览

热门推荐

通过挑战的用户

查看代码

相关试题

头条校招

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号