字节算法题——连续出题问题

题目描述

每个出题人都出了一些有趣的题目，现在想把这些题目组合成若干场考试出来，在选题之前，我们定出了每道题的难度系统。一场考试包含3道开放性题目，假设他们的难度从小到大分别为a,b,c，我们希望这3道题能满足下列条件：
a<=b<=c
b-a<=10
c-b<=10
一共出了n道开放性题目。现在我们想把这n道题分布到若干场考试中（1场或多场，每道题都必须使用且只能用一次），然而由于上述条件的限制，可能有一些考试没法凑够3道题，因此出题人就需要多出一些适当难度的题目来让每场考试都达到要求，你能计算出我们最少还需要再出几道题吗？

题目分析

题目看起来复杂，实际上思路很简单，因为只有每场考试三个题目只有一个限制条件：a<=b<=c，b-a<=10，c-b<=10，即max((b-a), (c-b))<=10。

所以可以先排序，后遍历数组,

1:相邻3个数满足相邻差均<=10,则三个可以为一组,不需要加新的题目;

2:第二个数-第一个数>=20;表示第一个数自成一组,需要添加2个题目;

3:第二个数-第一个数在10-20之间,这两个数为一组,需要添加1个题目;

4:第二个数-第一个数小于10,而第三个数-第二个数大于10,前两个题目为一组,需要添加1个题目。

第三点和第四点再写法上可以并为一点。

最后剩下的可能为1或者2个数,再判断一次即可。

代码实现

python实现

n = int(input().split()[0])
ques = sorted(map(int, input().split()))

re = 0
pos = 0
while(n-pos>=3):
    # max((b-a), (c-b))<=10,即三个题目可以分为一组
    if((ques[pos+1]-ques[pos])<=10 and (ques[pos+2]-ques[pos+1])<=10):
        pos+=3
    # 前两个相差大于20,至少需要增加2题
    elif((ques[pos+1]-ques[pos])>20):
        re+=2
        pos+=1
    # 前两个可以为一组
    else:
        re+=1
        pos+=2
# 剩余1个题目
if(n-pos==1):
    re+=2
# 剩余2个题目,有2种情况,一种增加一个题目,另一种增加4个题目
elif(n-pos==2):
    [a,b] = ques[-2:]
    if((b-a)<=20):
        re+=1
    else:
        re+=4
print(re)

C++实现

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> ques(n,0);
    for(int i=0;i<n;i++){
        cin>>ques[i];
    }
    // 排序
    sort(ques.begin(), ques.end());
    int re = 0;
    int pos = 0;
    // 遍历
    while(n-pos>=3){
        // max((b-a), (c-b))<=10,即三个题目可以分为一组
        if((ques[pos+1]-ques[pos])<=10 && (ques[pos+2]-ques[pos+1])<=10){
            pos+=3;
        }
        // 前两个相差大于20,至少需要增加2题
        else if((ques[pos+1]-ques[pos])>20){
            re+=2;
            pos+=1;
        }
        // 前两个可以为一组
        else{
            re+=1;
            pos+=2;
        }   
    }
    // 剩余2个题目,有2种情况,一种增加一个题目,另一种增加4个题目
    if(n-pos==2){
        if((ques[pos+1] - ques[pos])<=20){
            re+=1;
        }
        else{
            re+=4;
        }
    }
    // 剩余1个题目,增加2题
    else if(n-pos==1){
        re+=2;
    }
    cout<< re << endl;
    return 0;
}