首页 > 试题广场 >

头条校招

[编程题]头条校招

热度指数：17821 时间限制：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

输出

算法知识视频讲解

Java

牛客504357922号

1) 首先要知道 ACM模式的代码编写，有别于核心代码模式，ACM模式，没有基本的代码架子，需要自己写类Main（对于 Java），然后就是通过 Scanner这个类，去获取 System.in的输入

2）本题而言：

sc.nextInt()

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            // 升序
            Arrays.sort(a);
            // 可以放到当前一个考场的题目数
            int t = 1;
            int cnt = 0;
            for (int i = 1; i < n; i++) {
                if(t < 3) {
                    if(a[i] - a[i-1] <= 10){
                        // 可以放到一个考场的题目数加1
                        t++;
                    }else if(t == 1 && a[i] - a[i-1] <= 20) {
                        // 直接增加一个 中间的题目，来满足一个考场上的3道题目
                        cnt ++;
                        t = 3;
                    } else {
                        // 当前考场需要增加的题目数是到 3的差值
                        cnt += 3 - t;
                        // 继续初始化 可以放到一个考场的题目为1
                        t = 1;
                    }
                } else{  // 继续初始化 可以放到一个考场的题目为1                     t = 1;
                }
            }

            // 考题数 是与 3的差值累加
            cnt += 3 - t;
            System.out.println(cnt);
        }
    }
}

编辑于 2022-01-09 16:46:41 回复(1)

Java

衣有尘

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        sc.nextLine();
        int count = 0;
        String s = sc.nextLine();
        String [] sarray = s.split(" ");
        int [] intarray = new int[sarray.length];
        for (int i = 0;i < sarray.length;i++){
            intarray[i] = Integer.parseInt(sarray[i]);
        }
        Arrays.sort(intarray);
        for(int j = 0;j < intarray.length;){
            if (j+2<intarray.length) {
                if ((intarray[j + 1] - intarray[j]) <= 10 && (intarray[j + 2] - intarray[j + 1]) <= 10) {
                    j += 3;
                    //break;
                } else if ((intarray[j + 1] - intarray[j]) <= 10 && (intarray[j + 2] - intarray[j + 1]) > 10) {
                    j = j + 2;
                    count += 1;
                    //break;
                } else if ((intarray[j + 1] - intarray[j]) > 20) {
                    j = j + 1;
                    count += 2;
                    //break;
                } else if ((intarray[j + 1] - intarray[j]) > 10 && (intarray[j + 1] - intarray[j]) <= 20) {
                    j = j + 2;
                    count += 1;
                    //break;
                }
            }
            else if(j+1<intarray.length){
                if ((intarray[j + 1] - intarray[j]) > 20) {
                    j = j + 1;
                    count += 2;
                    break;
                }
                else if ((intarray[j + 1] - intarray[j]) < 20) {
                    j = j + 1;
                    count += 1;
                    break;
                }
            }
            else if(j<intarray.length){
                count+=2;
                break;
            }
        }
        System.out.println(count);
    }
}

发表于 2021-03-07 01:49:10 回复(0)

Java

OKO

import java.util.*;

public class Main {

   public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);
       int n = scan.nextInt();
       int[] arr = new int[n];
       for (int i = 0; i < n; i++) {
           arr[i] = scan.nextInt();
       }
       Arrays.sort(arr);
       int t = 1;
       int incr = 0;
       for (int i = 1; i < n; i++) {
           if (t < 3) {

               int j = arr[i];
               if (arr[i] - arr[i - 1] <= 10) {
                   t++;
               } else if (t == 1 && arr[i] - arr[i - 1] <= 20) {
                   incr += 1;
                   t = 3;
               } else {
                   incr += 3 - t;
                   t=1;
               }
           }else {
               t=1;
           }
       }
       incr+=3-t;
       System.out.println(incr);
   }
}

发表于 2018-10-03 11:51:55 回复(0)

Java

黄小斜

先排序，相邻数差超过10时加入新题，最后如果不是3的倍数，则加到3的倍数为之
import java.util.Arrays;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int []arr = new int[n];
        for (int i = 0;i < n;i ++) {
            arr[i] = scanner.nextInt();
        }
        System.out.println(num(arr));
    }
    public static int num(int []arr) {
        Arrays.sort(arr);
        int cnt = 0;
        for (int i = 1;i < arr.length;i ++) {
            if (arr[i] - arr[i - 1] <= 10) {

            }
            else {
                int d = arr[i] - arr[i - 1];
                if (d % 10 == 0) {
                    cnt += d/10 - 1;
                }else {
                    cnt += d % 10;
                }
            }
        }
        while ((cnt + arr.length)% 3 != 0) {
            cnt ++;
        }
        return cnt;
    }
}

发表于 2018-06-06 21:18:28 回复(0)

Java

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)

Java

Angelべ天行

import java.util.*;

public class Main {
public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
int count=0;
for(int i=0;i<a.length-1;i++){
if(a[i+1]-a[i]>10&&a[i+1]-a[i]<=20){
count++;
}
}
int p=a.length+count;
int q=count;
if(p%3==1){
q=count+2;
}else if(p%3==2){
q=count+1;
}
System.out.println(q);
}
}
}

发表于 2018-03-22 15:22:02 回复(0)

Java

傻傻傻傻

//大概就是简单分析下以下六种情况吧
/**
4 15 16 17 18
4 25 26 27 28
4 5 16 17 18
4 5 26 27 28
4 5 6 17 18 19
4 5 6 27 28 29
*/
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int total = in.nextInt();
            int[] array = new int[total];
            for (int i = 0; i < total; i++)
                array[i] = in.nextInt();
            Arrays.sort(array);
            int count = 0;
            int flag = 0;
            for (int i = 1; i < total; i++) {
                if (flag == 3) {
                    flag = 0;
                    continue;
                }
               flag++;
               if (array[i] - array[i-1] <= 20 && array[i] - array[i-1] > 10) {
                   count++;
                   if (flag == 1) flag = 3;
               } else if (array[i] - array[i-1] > 20){
                   if (flag == 1) count += 2;
                   if (flag == 2) count++;
               }
            }
            int res = (count + total) % 3;
            if (res != 0) count += 3 - res;
            System.out.println(count);

        }
    }
}

编辑于 2017-12-11 19:05:13 回复(0)

Java

牛客8805036号

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {

   public static void main(String[] args) {
       // TODO Auto-generated method stub
       Scanner sc = new Scanner(System.in);
       while(sc.hasNext()) {
           int n = sc.nextInt();
           ArrayList<Integer> timu = new ArrayList<Integer>();
           for(int i =0;i<n;i++) {
               timu.add(sc.nextInt());
           }
           Collections.sort(timu);
           calculateTimuNum(timu);
       }
   }

   private static void calculateTimuNum(ArrayList<Integer> timu) {
       int needTimu = 0;
       for(int i = 0;i<timu.size()-1;i++) {
           if(timu.get(i+1) - timu.get(i) > 10 && timu.get(i+1) - timu.get(i) <=20
                   ) {
               if((i+1+needTimu)%3==1) {
                   i++;
                   needTimu++;
               }else if((i+1+needTimu)%3==2) {
                   needTimu+= 1;
               }
           }else if(timu.get(i+1) - timu.get(i) > 20 ) {
               if((i+1+needTimu)%3==1) {
                   needTimu+= 2;
               }else if((i+1+needTimu)%3==2) {
                   needTimu+= 1;
               }

           }
       }
       int left = (timu.size()+needTimu)%3;
       if(left != 0) {
           needTimu+=3-left;
       }
       System.out.println(needTimu);
   }

}

发表于 2017-10-23 12:26:02 回复(0)

Java

fsdfsd

大家想复杂了。。。一场考试三道题目，并且每到题目必须使用且只能用一次，所有总共的题目一定是3的倍数

所以结果是：如果n是3的倍数就出0道题目，如果不是3的倍数就是3-n%3

代码如下：

import java.util.Scanner;

public class Main{
   public static int fun(int[] a,int n)
   {
       int s = n%3;
       if(s==0)
           return 0;
       else
           return 3-s;

   }
   public static void main(String[] args) {
       // TODO Auto-generated method stub
       Scanner sc = new Scanner(System.in);
       while(sc.hasNext())
       {
           int n = sc.nextInt();
           int[] a = new int[n];
           for(int i=0;i<n;i++)
               a[i] = sc.nextInt();
           System.out.println(fun(a, n));
       }
   }

}

发表于 2017-10-15 19:27:54 回复(4)

Java

北冥有鱼。

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

排序之后，

可以以三个为一组判断，定义一个count记录组内成员当前数量，定义K记录需要添加的数量，遍历数组，定义为j。则共有以下情况：

count=0时，代表组内没有成员，是一个新的组，从第二个开始与前一个比较：

（1）后一个—前一个<10,他俩可以分为一组，count=2，K不变，J+1

（2） 10<后一个—前一个<20,这两个可以为一组，中间需要补一个，count=3（count置0也可，都表示组满）,K+1,J+2,下一次循环即为下一组的后一个与它的前一个比

（3）后一个—前一个>20,不能分到一组，此组需补充两个，组满，count=3，K+2，J++

count=2时，组内已经有两个成员：

（1）后一个—前一个<10，可以加进去，count=3，K不变

（2）后一个—前一个<10，不可以加进这组，需要补一个，K+1，count=3,J++

最后，判断总数是否为三的倍数，判断还要再补几个

* */
public class Main1 {

   public static void main( String[] args ) {
       Scanner scan=new Scanner(System.in);
       while(scan.hasNext()){
           int count=0,k=0,sum=0;
           int n=scan.nextInt();
           /*String str=scan.nextLine();
           String[] ch1=str.split(" ");
           StringBuffer sb=new StringBuffer();
           for(int j=0;j<ch1.length;j++){
               sb.append(ch1[j]);
           }
           char[] ch=sb.toString().toCharArray();*/
           int ch[]=new int[n];
           for(int i=0;i<n;i++){
               ch[i]=scan.nextInt();
           }

           Arrays.sort(ch);
           //   System.out.println("ch.length:"+ch.length);
           for(int j=1;j<ch.length;){
               if(count==0){
                   if(ch[j]-ch[j-1]<=10){
                       //System.out.println("0+J:K:ch[j]:"+j+k+ch[j]);
                       count=2;j++;

                   }else if(ch[j]-ch[j-1]>=10&&ch[j]-ch[j-1]<=20){
                       count=0;j+=2;k++;
                   }else if(ch[j]-ch[j-1]>=20){
                       count=0;j++;k+=2;
                   }
               }else if(count==2){
                   if(ch[j]-ch[j-1]<=10){
                       //System.out.println("1+J:K:ch[j]:"+j+""+k+ch[j]);
                       count=0;j+=2;

                   }else{
                       //System.out.println("1.1+J:K:ch[j]:"+j+k+ch[j]);
                       count=0;j++;k++;

                   }
               }
           }
           sum=n+k;
           //System.out.println("sum:"+sum);
           if(sum%3==1){
               k+=2;
               //System.out.println("2.1.K:"+k);
           }else if(sum%3==2){
               k+=1;
               //System.out.println("2.2.K:"+k);
           }
           System.out.println(k);

       }
   }

}

发表于 2017-09-07 21:11:42 回复(0)

Java

天栎

/*通过了所有测试 */

import java.util.Arrays;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

int[]arr=new int[n];

for(int i=0;i<n;i++){

arr[i]=sc.nextInt();

}

Arrays.sort(arr);

int flag = 0;

int count=0;

for(int i=0; i<n-1;){

if((arr[i+1]-arr[i])>=20){

count = count+2;

i = i+1;

continue;

}

else if((arr[i+1]-arr[i])>10){

flag= (i+1+count)%3;

count = count+1;

	        		 if(flag==1)

{i = i+2;

continue;

}

else if(flag==2)

{i = i+1;

}

continue;

}

else if((arr[i+1]-arr[i])<=10){

i = i+1;

continue;

}

if((n+count)%3==0){

}

else {count= count+3-(n+count)%3;

}

System.out.println(count);

}

发表于 2017-08-22 16:36:02 回复(0)

Java

钱塘江

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

public class Main {  public static void main(String[] args) {    Scanner in = new Scanner(System.in);    int n = in.nextInt();  int[] scope = new int[n];    for(int i = 0; i < n; i++) {  scope[i] = in.nextInt();  }    //排序  Arrays.sort(scope);    //计算排序后的相互差值  int[] diff = new int [n - 1];  for(int i = 0; i < n - 1; i++) {  diff[i] = scope[i + 1] - scope[i];  }    int m = 0;    int i = 0;  int l = 0;  while(i < n -1) {  if(l == 2) {  l = 0;  } else if(diff[i] <= 10) {  l++;  } else {  m += (2 - l);  l = 0;  }  i++;  }    m += (2 - l);  System.out.println(m);  }   }

发表于 2017-08-22 16:34:01 回复(0)

Java

心生杂念

import java.util.Scanner;

public class Main{
	public static void quicksort(int[] a,int low,int high){
		if(low>=high){
			return;
		}
		int i = low;
		int j = high;
		int p = a[low];
		while(i<j){
			while(a[j]>p&&i<j)
				j--;
			if(i!=j){
				a[i] = a[j];
				i++;
			}
			while(a[i]<p&&i<j)
				i++;
			if(i!=j){
				a[j] = a[i];
				j--;
			}
		}
		a[i] = p;
		quicksort(a, low, i-1);
		quicksort(a, i+1, high);
	}
	
	public static void main(String[] args) {
		Scanner scanner= new Scanner(System.in);
		int n = scanner.nextInt();
		int[] d = new int[n];
		int count = 0;
		for(int i=0;i<n;i++){
			d[i] = scanner.nextInt();
		}
		quicksort(d, 0, d.length-1);
		for(int i=0;i<n;i++){
			if(i==n-1){
				count += 2;
				break;
			}
			if(i==n-2){
				int a = d[i];
				int b = d[i+1];
				if(b-a<=10&&b>=a){
					count += 1;
					break;
				}
				else if(b-a<=20&&b>=a){
					count += 1;
					break;
				}
				else{
					count += 4;
					break;
				}
			}
			else{
				int a = d[i];
				int b = d[i+1];
				int c = d[i+2];
				if(b-a<=10&&b>=a){
					if(c-b<=10&&c>=b){
						count += 0;
						if(i==n-3){
							break;
						}
						i += 2;
					}
					else{
						count += 1;
						i++;
					}
				}
				else if(b-a<=20&&b>=a){
					count += 1;
					i++;
				}
				else{
					count += 2;
				}
			}
		}
		System.out.println(count);
	}
}

编辑于 2017-08-22 15:58:33 回复(1)

Java

****

    importjava.util.*;   
    publicclassMain{   
        publicstaticvoidmain(String[] args)   
            {   
            Scanner sc=newScanner(System.in);   
           intn=sc.nextInt();   
            int[]arr=newint[n];   
            for(inti=0;i<n;i++){   
                arr[i]=sc.nextInt();   
            }   
            Arrays.sort(arr);   
            intcount=0;   
            inttemp=1;   
            intflag=1;   
            for(inti=temp;i<n;i++){   
                if(flag==1){   
                    if((arr[i]-arr[i-1])>20){   
                    count+=2;   
                        
                }   
                   if((arr[i]-arr[i-1])>10&&(arr[i]-arr[i-1])<=20){   
                    count+=1;   
                    i+=1;   
                }   
                    if((arr[i]-arr[i-1])<=10){   
                        flag++;   
                        continue;   
                    }   
                }   
                    
                if(flag==2){   
                     if((arr[i]-arr[i-1])>10){   
                    count+=1;   
                     }   
                    if((arr[i]-arr[i-1])<=10){   
                        flag=1;   
                        i+=1;   
                    }   
                }   
            }   
            if((count+n)%3==0){   
                System.out.println(count);   
            }   
            if((count+n)%3==1){   
                System.out.println(count+2);   
            }   
            if((count+n)%3==2){   
                System.out.println(count+1);   
            }   
               
                
        }   
    }   
           

添加笔记

编辑于 2017-08-16 13:48:55 回复(0)

Java

Jungggle

import java.util.PriorityQueue;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

try (Scanner scanner = new Scanner(System.in)) {

while (scanner.hasNext()) {

int n = scanner.nextInt();

PriorityQueue<Integer> queue = new PriorityQueue<>();

for (int i = 0; i < n; i++) {

queue.offer(scanner.nextInt());

}

int mustAdd = 0;

if (n % 3 != 0)

mustAdd = 3 - n % 3;

int last = queue.poll();

int sum = 0;

while (!queue.isEmpty()) {

int now = queue.poll();

if (now - last > 10) {

sum += ((now - last) / 10);

if ((now - last) % 10 == 0)

sum--;

}

last = now;

}

if (sum <= mustAdd)

System.out.println(mustAdd);

else {

sum -= mustAdd;

int yu = sum % 3;

if (yu == 0)

System.out.println(sum + mustAdd);

else

System.out.println(3 * (sum / 3 + 1) + mustAdd);

}

k eng 坑多

发表于 2017-08-15 17:10:28 回复(0)

Java

牛妹同桌

import java.util.Arrays; import java.util.Scanner;  /**  * Created by albert on 2017/7/4.  * 代码好乱复制过来。
*/ public class Main {  public static void main(String[] args) {
        Scanner in = new Scanner(System.in);  int n = in.nextInt();  int[] diffic = new int[n];  int i = 0;  while (in.hasNextInt()){
            diffic[i++] = in.nextInt();  }
        in.close();    Arrays.sort(diffic);  int count = 0; 
       int size = 3;  int j;
      for (j = 0; j <= n-3; j = j+size) {  if ((diffic[j+1] - diffic[j])<=10) {  if ((diffic[j + 2] - diffic[j + 1]) <= 10) 
                    { continue;  }  else {
                    size = 2;  count++;  }
            }else if (diffic[j+1] - diffic[j] <= 20){
                count++;  size = 2;  }  else {
                size = 1;  count = count+2;  }
        } if (n - j == 2){  if (diffic[j+1]-diffic[j] <=20)
                count++;  else count += 4;    }  if (n - j == 1)
            count += 2;    System.out.println(count);  }
}