首页 > 试题广场 >

头条校招

[编程题]头条校招
  • 热度指数：17799 时间限制：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
算法知识视频讲解
添加回答
C/C++
卷积神经网络哦头像 卷积神经网络哦

划窗O(n) 分支挺多 代码有点乱 3个一组分4种情况 先从小到大排个序O(nlogn) 
下标永远指向第一个数
第1种： 这三个都满足要求 下标直接+3
第2种： 第二个比第一个大超过20 那么第一个后面添加2个数 下标+1
第3种：第二个比第一个大超过10 但不大于20  中间加1个即可 下标+2
第4种：第一第二满足 第三个第二个不满足 不管怎样 第二个后面添加1个 下标+2
第3第4可以合并 但是原理不一样 


#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 3;
int a[maxn];
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    if(n == 1) printf("%d\n", 2);  
    sort(a, a + n);
    else if(n == 2) {
        if(a[1]-a[0] > 20) printf("%d\n", 4);
        else printf("%d\n", 1);
    }
    else{
        int l = 0, add = 0;
        while(l < n - 2){ 
            if(a[l+1]-a[l] <= 10 && a[l+2] - a[l+1] <= 10) l += 3;
            else if(a[l+1] - a[l] > 20) {add += 2; l += 1;}
            else if(a[l+1]-a[l] <= 20 && a[l+1]-a[l] > 10) {add++;l+=2;}
            else if(a[l+1]-a[l] <= 10 && a[l+2]-a[l+1] > 10) {add++;l+=2;}
            if(l == n - 1) add += 2;
            if(l == n - 2) {
                if(a[l+1]-a[l] > 20) add += 4;
                else add += 1;
            } 
        }
        printf("%d\n", add);
    } 
}

编辑于 2018-09-21 12:55:19 回复(7)
C/C++
岚の风头像 岚の风 
//看了好多种dp解法。。。感觉好像不太对，对于10 30 50这种样例
//或者21 40 69 77这种在中间加入一个数的问题，不能正确输出，只是数据太弱了，
//都能通过。
//仔细想了下 1 ≤ di ≤ 100 排序之后间距大于10的（input[i]-input[i-1]>10）
//数据，最多只会有10个，因此直接暴力+贪心即可，
//每次发现间距大于10并且前面那些数不是3的整数倍，
//就直接加一个数，显然要加最后那个数+10的那个数字，
//因为这是最后可能让新加的数可能跟后面的数据重新连接起来的情况，
//然后extra计数++，重新排序，重新再看是否符合要求，
//因为前面说的di的范围问题，暴力循环即可，不会超时

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        vector<int> input(n,0);
        for(int i=0; i<n; i++)
        {
            cin>>input[i];
        }
        int extra=0;
        while(true)
        {
            sort(input.begin(),input.end());
            bool flag=true;
            int now=1;
            for(int i=1;i<=input.size();++i)
            {
                if( (input[i]-input[i-1]>10 || i==input.size() )&& now%3 )
                {
                    input.insert( input.begin()+i, input[i-1]+10 );
                    extra++;
                    flag=false;
                    break;
                }
                now++;
                now%=3;
            }
            if(flag)
                break;
        }
        cout<<extra<<endl;
    }
    return 0;
}

编辑于 2018-05-21 13:03:56 回复(6)
Jimmy_gg头像 Jimmy_gg 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

int main() {
    using namespace std;
    int n;
    while (cin >> n) {
        multiset<int> mark;
        for (int i = 0; i < n; i++) {
            int input;
            cin >> input;
            mark.insert(input);
        }
        multiset<int>::iterator itor = mark.begin();
        ++itor;
        multiset<int>::iterator iter = mark.begin();
        int cnt = 1;
        for (; itor != mark.end(); itor++) {
            bool flag = false;
            while (*itor - *iter > 10 && (cnt % 3)) {
                int temp = *iter + 10;
                mark.insert(temp);
                iter = mark.find(temp);
                cnt++;
                flag = true;
            }
            iter++;
            if (!flag) {
                cnt++;
            }
        }
        int ret = 0;
        if (mark.size() % 3) {
            ret += 3 - (mark.size() % 3);
        }
        int ans = mark.size() - n + ret;
        cout << ans << endl;
    }
    return 0;
}
模拟一下过程即可，不过，最后的模运算要注意，排除0的情况，否则只能通过80%
发表于 2017-07-04 09:03:37 回复(9)
Java
hnyd头像 hnyd

不需要动态规划，思路很简单，先将数组从小到大依次排列，遍历数组找出相邻两个数差值大于10的个数，将这个数和n相加然后对3取模，差几个补几个就行了，代码如下：

import java.util.Arrays;
import java.util.Scanner;

public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int count = sc.nextInt();
    int[] array = new int[count];
    for (int i = 0; i < count; i++) {
      array[i] = sc.nextInt();
    }
    Arrays.sort(array);
    int increase = 0;
    for (int i = 0; i < count - 1; i++) {
      if ((array[i + 1] - array[i] > 10)) {
        increase++;
      }
    }
    int tmp = (count + increase) % 3;
    System.out.println(tmp == 0 ? increase : increase + 3 - tmp);
  }
}
发表于 2018-03-25 00:04:21 回复(6)
Fukui123头像 Fukui123
我的想法是：首先需要一个数t，确定是不是一组的，然后是一组的情况下，判断是否大于10，大于10后再判断是否大于二十，如果小于20，那么只用加一个数即可，如果大于20，则需要看t的值来判断是加一个数还是2个数。代码如下： 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
    {
    int n;
    cin>>n;
    vector<int> hard(n,0);
    for(int i = 0;i<n;i++)
        {
        cin>>hard[i];
    }
    sort(hard.begin(),hard.end());
    int result = 0;
    int t = 1;
    for(int i = 0;i<n-1;i++)
        {
        if(t<3)
            {
            if(hard[i+1] - hard[i]>10)
            {
				if((hard[i+1] - hard[i])<=20)
                    {
                    result++;
                    t++;
                }
                else if(t == 1)
                {
                    result+=2;
                    t+=2;
                }
                else if(t == 2)
                    {
                     result+=1;
                     t+=1;
                }
            }
        }
        else{
            t = 1;
        }
    }
    while((n+result)%3 != 0)
        {
        result++;
    }
    cout<<result<<endl;
    return 0;
}

发表于 2017-08-24 16:56:55 回复(2)
fengcq头像 fengcq
使用动态规划：从右到左依次生成dp[i],代表i到n的最少出题数，那么dp[0]就是答案。其他人的很多解法都是去添加题模拟，且没有考虑到排序之后的这样的情况：10 15 20   50 55 58；他们都是直接看差值是否大于10或20去加题目，然而该题却不用加任何题目。
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
int main(){
int n;
    while(cin>>n){
        vector<int> input(n,0);
        for(int i=0;i<n;i++){
            cin>>input[i];
        }
        sort(input.begin(),input.end());
        vector<int> dp(n,0);
dp[n-1]=2;
if(n==1){
cout<<dp[0]<<endl;
continue;
}
for(int i=n-2;i>=0;i--){
dp[i]=dp[i+1]+2;
}

if(input[n-1]-input[n-2]<20)
dp[n-2]=min(dp[n-2],1);
else dp[n-2]=min(dp[n-2],2+dp[n-1]);

if(n==2){
cout<<dp[0]<<endl;
continue;
}
        
if(input[n-2]-input[n-3]<10){
if(input[n-1]-input[n-2]<10){
dp[n-3]=min(dp[n-3],0);
}
else{
dp[n-3]=min(dp[n-3],1+dp[n-1]);
}
}else if(input[n-2]-input[n-3]<20){
dp[n-3]=min(dp[n-3],1+dp[n-1]);
}
else dp[n-3]=min(dp[n-3],2+dp[n-2]);
for(int i=n-4;i>=0;i--){
if(input[i+1]-input[i]<10){
if(input[i+2]-input[i+1]<10){
dp[i]=min(dp[i],dp[i+3]);
}
else{
dp[i]=min(dp[i],1+dp[i+2]);
}
}else if(input[i+1]-input[i]<20){
dp[i]=min(dp[i],1+dp[i+2]);
}
else{
dp[i]=min(dp[i],2+dp[i+1]);
}
}
cout<<dp[0]<<endl;
    }
    return 0;
}
发表于 2017-08-05 17:15:16 回复(4)
油条头像 油条
//根本不需要动态规划，数列升序排列后，按相临两数差大于10进行split，每组数按3取模，各组模求和即可，简单高效易理解！
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
cin >> n;
int d[100000];
for (int i = 0; i < n; i++)
{
cin >> d[i];
}
sort(d, d + n);
int li=-1,x=0,gap = 0,dx=0;

for (int i = 0; i < n; i++)
{
if (i < n - 1)
{
if (d[i + 1] - d[i]>10)
{
gap = i - li;
if (gap % 3 == 0) dx = 0;
else dx = 3 - gap % 3;
x = x + dx;
li = i;
}

}
else
{
gap = i - li;
if (gap % 3 == 0) dx = 0;
else dx = 3 - gap % 3;
x = x + dx;
}
}
cout << x << endl;
}
发表于 2017-08-23 22:51:01 回复(7)
稳稳滴幸福头像 稳稳滴幸福 
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    vector<int> a;
    cin>>n;
    for(int i = 0; i<n; i++)
    {
        int v;  cin>>v;
        a.push_back(v);
    }
    int x = a.size()%3;
    if (x == 0)
        cout<<0;
    else
    cout<<3-x;
}
其实这道题在忽悠大家，题目描述了一大堆都没用，仔细想一下，好像是只要出题数目能被3整除就满足所有条件，不能被3整除补足就行了。出题者满足要求就行了，只要能总题量能被3整除就满足考场需求，至于其他要求我们不用管，我们只要算数量。
连排序都不需要
编辑于 2018-03-26 21:48:03 回复(9)
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)
木析头像 木析
排序后贪心取值 
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> arr(n,0);
    for(int i=0;i<n;i++) {
        cin>>arr[i];
    }
    sort(arr.begin(),arr.end());
    int res=0;
    int count=1; //记录当前选出的题数
    int pre=arr[0]; //记录当前题数的最高难度系数
    for(int i=1;i<n;i++) {
        if(count==3) { //题量已满，导出，开始下一轮
            pre=arr[i];
            count=1;
            continue;
        }
        if(arr[i]-pre<=10) {
            pre=arr[i];
        }else{
            pre=arr[i]+10; //补一题
            i--;
            res++;
        }
        count++;
    }
    res+=3-count;
    cout<<res<<endl;
    return 0;
}


发表于 2021-05-07 21:20:12 回复(0)
BValue头像 BValue 
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1E5 + 10;
int a[N];
int main(){
    int n;    scanf("%d", &n);
    for(int i = 0; i < n; i ++ )    cin >> a[i];
    sort(a, a + n);
    int cnt = 0, i = 0;
    int num = 0;
    while(i < n){
        if(a[i] + 10 < a[i + 1]){
            cnt ++ ;
            a[i] += 10;
            num ++ ; 
        }else{
            i ++ ;
            num ++ ;
        }
        if(num == 3)    num = 0;
    }
    if(num)    cnt += (3 - num);
    cout << cnt << endl;
    return 0;
}
发表于 2021-03-27 09:52:47 回复(0)
pein531头像 pein531
先对已有题目的难度进行排序，每场考试只有在题目难度最接近的情况下才能尽可能保证少出新题。然后使用贪心算法安排每一场考试。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strD = br.readLine().trim().split(" ");
        int[] d = new int[n];
        for(int i = 0; i < n; i++) d[i] = Integer.parseInt(strD[i]);
        int p = 1;        // 初始化一场考试，此时它只有一道考题d[0]，p表示目前试卷中的考试题数
        int count = 0;    // 初始化的附加题数
        Arrays.sort(d);
        for(int i = 1; i < n; i++){
            if(p < 3){
                if(d[i] - d[i - 1] <= 10){
                    // 如果下一道题的难度与目前试卷中最难的题难度相差在10以内，就可以直接把题目d[i]加入试卷中，无需重新出题
                    p += 1;
                }else if(p == 1 && d[i] - d[i - 1] <= 20){
                    // 如果目前试卷中只有一道题，且下一道题的难度与目前试卷中最难的题难度相差在10以上20以内，
                    // 就需要再出一道中间难度的题，然后把题目d[i]和新出的题都加入到试卷中
                    p += 2;
                    count += 1;
                }else{
                    // 其他情况下不能通过从已出的题中选题加入试卷中，只能重新出3-p题加入试卷中，d[i]用来开启一场新的考试
                    count += 3 - p;
                    p = 1;
                }
            }else{
                // 一场考试题已满，利用d[i]重新开启一场考试
                p = 1;
            }
        }
        // 防止最后一道题d[n-1]用完后，试卷还不足3题
        count += 3 - p;
        System.out.println(count);
    }
}


发表于 2021-01-28 21:29:59 回复(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)
C/C++
忠孝201803262252731头像 忠孝201803262252731 
#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin>>n;
    // questions数组保存出题的难度 
    int * questions = new int[n+1];
    // dp[i]表示出了i题时还需出题的最少个数 
    int * dp = new int[n+1];
    for(int i=1;i<=n;i++){
        cin>>questions[i];
    }
    // 题目难度升序排序 
    sort(questions+1,questions+n);
    // 小于3道时的情况，直接输出
    if(n==1){
        cout<<2<<endl;
        return 0;
    }
    if(n==2){
        if(questions[2]-questions[1]<=10){
            dp[2] = 1;
            cout<<dp[2]<<endl;
            return 0;
        }
        if(questions[2]-questions[1]>10){
            dp[2] = (questions[2]-questions[1])/10;
            cout<<dp[2]<<endl;
            return 0;
        }
    }
    if(n==3){
        if(questions[3]-questions[2]<=10 && questions[2]-questions[1]<=10){
            dp[3] = 0;
            return 0;
        }
        if(questions[2]-questions[1]>10 && questions[3]-questions[2]<10){
            dp[3] = (questions[2]-questions[1])/10;
            cout<<dp[3]<<endl;
            return 0;
        }
        if(questions[2]-questions[1]>10 && questions[3]-questions[2]>10){
            dp[3] = (questions[2]-questions[1])/10+(questions[3]-questions[2])/10;
            cout<<dp[3]<<endl;
            return 0;
        }
    }
    // 从下到上计算dp[i]
    dp[0] = 0;
    dp[1] = 2;
    if(questions[2]-questions[1]<=10){
       dp[2] = 1;
    }
    if(questions[2]-questions[1]>10){
        dp[2] = (questions[2]-questions[1])/10;
    }
    if(n==3){
        if(questions[3]-questions[2]<=10 && questions[2]-questions[1]<=10){
            dp[3] = 0;
            return 0;
        }
        if(questions[2]-questions[1]>10 && questions[3]-questions[2]<10){
            dp[3] = (questions[2]-questions[1])/10;
            cout<<dp[3]<<endl;
            return 0;
        }
        if(questions[2]-questions[1]>10 && questions[3]-questions[2]>10){
            dp[3] = (questions[2]-questions[1])/10+(questions[3]-questions[2])/10;
            cout<<dp[3]<<endl;
            return 0;
        }
    }
    for(int i=4;i<=n;i++){
        dp[i] = dp[i-1]+2; // 每多出一道题，为了能被3整除就还需再出2道
        if(i>1 && questions[i]-questions[i-1]>20){
            //如果i道比前一道难度大20，则选择为i道再出两道或为第i-2道再出一道中的最优解 
            dp[i] = min(dp[i],dp[i-2]+1);
        }
        // 如果连续三道题都满足差值小于等于10，则选择为i道再出两道或无需为i题再出新题 
        if(i>2 && questions[i]-questions[i-1]<=10 && questions[i-1]-questions[i-2]<=10){
            dp[i] = min(dp[i],dp[i-3]); 
        }
    }
    cout<<dp[n]<<endl;
    delete[] dp;
    delete[] questions;
    return 0;
}
编辑于 2020-03-15 14:13:32 回复(2)
JC-Ge头像 JC-Ge
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] d = new int[n];
        // 取得值
        for(int i = 0;i < n;i++){
            d[i] = input.nextInt();    
        }
        // 最后要添加的题数
        int result = 0;
        // 临时存储难度值
        int t = 0;
        // 用冒泡进行从小到大的排序
        for(int p = 0;p < d.length - 1;p++){
            for(int q = p;q < d.length - 1;q++){
                if(d[q] > d[q + 1]){
                    t = d[q];
                    d[q] = d[q+1];
                    d[q+1] = t;
                }else ;
            }
        }
        // 定义接收变量
        int a = 0;
        int b = 0;
        int c = 0;
        int i = 0;
        // 从小的取 每三个看符不符合规矩
        while(d.length - i >= 3){
            a = d[i];
            b = d[i+1];
            c = d[i+2];
            // 取出的前两道题符合约束
            if(b-a<=10){
                i++;
                // 取出的后两道符合约束
                if(c-b<=1) i+=2;
                // 不符合
                else {
                    result++;
                    i++;
                }
            }
            // 取出的前两道不符合约束
            else{
                // 前两道题难度差距小于等于20
                 if(b - a <= 20){
                     result++;
                     i+=2;
                 }
                 // 大于20
                 else{
                         result+=2;
                         i++;
                     }
            }
        }
        // 最后剩两道题
        if(d.length - i == 2){
            int x = d[i];
            int y = d[i + 1];
            if(y - x <= 20)result++;
            else{
                result+=4;
            }
        }
        // 剩一道题
        else if(d.length - i == 1){
            result+=2;
        }
        // 一道不剩
        else if(d.length - i == 0);
        // 输出最后结果
        System.out.println(result);
    }
}

发表于 2018-11-07 23:00:43 回复(0)
C/C++
黄Fun头像 黄Fun 
通过率80%，找不到原因···
#include<stdio.h>

#define MOD 3

void sort(int d[], unsigned int n);

int main()
{
    int n;
    int i, flag;
    int add, cnt;
    scanf("%d",&n);
    int ary[n];
    for(i = 0; i < n; ++i)
        scanf("%d",ary+i);
    sort(ary, n);
    add = 0;
    cnt = 1;
    flag = 0;

    for(i = 1; i < n; ++i)
    {
        if(ary[i] - ary[i-1] <= 10)
            ++cnt;
        else if(ary[i] - ary[i-1] <= 20 && flag == 0)
        {
            flag = 1;
            ++cnt;
        }
        else if(cnt % MOD != 0)
        {
            add += MOD - cnt % MOD;
            cnt = 1;
            flag = 0;
        }
    }
    if(cnt != 0)
        add += MOD - cnt % MOD;
    printf("%d\n", add);

}

void sort(int d[], unsigned int n)
{
    int i, j,temp;
    for(i = 0; i < n; ++i)
    {
        for(j = i+1; j < n; j++)
            if(d[i] > d[j])
            {
                temp = d[i];
                d[i] = d[j];
                d[j] = temp;
            }
    }
}

发表于 2018-09-20 10:52:11 回复(0)
C/C++
LiuShice头像 LiuShice
// 其实贪心就可以解决，写出所有的情况，依次判断即可

#include "iostream"
#include "set"
#include "deque"
#include "algorithm"

using namespace std;

int main(){
    multiset<int> ms;
    int n;
    cin>>n;
    for(int i = 0; i < n; ++i){
        int tmp;
        cin>>tmp;
        ms.insert(tmp);
    }
    deque<int> dq(ms.begin(), ms.end());
    int count = 0;
    int i = 0;
    while(i < dq.size()){
        if(i+1 < dq.size()){
            if(dq[i+1] - dq[i] <= 10){
                if(i+2 < dq.size()){
                    if(dq[i+2] - dq[i+1] <= 10){
                        i+=3;
                        continue;
                    }
                    else{
                        count++;
                        i+=2;
                        continue;
                    }
                }
                else{
                    count++;
                    break;
                }
            }
            else if(dq[i+1] - dq[i] <= 20){
                count++;
                i += 2;
                continue;
            }
            else{
                count+=2;
                i++;
                continue;
            }
        }
        else{
            count+=2;
            break;
        }
    }
    cout<<count<<endl;
    return 0;
}
发表于 2018-08-24 17:38:19 回复(0)
©☞陨辰☜℡头像 ©☞陨辰☜℡ 
时间复杂度较大，还望别嫌弃
题目其实很简单，不需要动态规划，我们将输出排序后判断相邻两个的差值就可以确定要插入几个，要满足差值小于等于10
则只需要其差值为11倍数时进行插入，插入的数量为t=(a[i+1]-a[i])/11,然后t+n的值为元素总数，再对不够3个的补全即可
#include<algorithm>
using namespace std;
int main()
{
    int n,k;
    cin>>n;
    vector<int> a(n);
    while(cin>>k)
    {
       a.push_back(k); 
    }
    sort(a.begin(),a.end());
    int t=0;
    for(int i=0;i<n-1;i++)
    {
        t+=(a[i+1]-a[i])/11;
    }
    (n+t)%3?cout<<(3-(n+t)%3)+t:cout<<t;
    return 0;
}

发表于 2018-08-22 14:53:10 回复(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)
C/C++
nbgao头像 nbgao 
#include <iostream> #include <algorithm> using namespace std; int main() {     int n,a[100007],result=0;     cin>>n;     for(int i=0;i<n;i++)         cin>>a[i];     sort(a,a+n);     int j=-1,d,b;     for(int i=0;i<n;i++)     {         if(i<n-1)         {             if(a[i+1]-a[i]>10)             {                 b = i - j;                 if(b%3==0)                     d = 0;                 else                     d = 3 - b%3;                 result += d;                 j = i;             }         }else{             b = i - j;             if(b%3==0)                 d = 0;             else                 d = 3 - b%3;             result += d;         }     }     cout<<result<<endl;     return 0; }


发表于 2018-01-09 00:55:54 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

头条校招

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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