算法|科大讯飞2019暑期实习笔试题

一、改成绩

题目：

　　华老师的n个学生参加了一次模拟测验，考出来的分数很糟糕，但是华老师可以将成绩修改为[0,100]中的任意值，所以他想知道，如果要使所有人的成绩的平均分不少于X分，至少要改动多少个人的分数？

输出和输出说明：

输入

第一行一个数T，共T组数据（T≤10）

接下来对于每组数据：

第一行两个整数n和X。（1≤n≤1000, 0≤X≤100）

第二行n个整数，第i个数Ai表示第i个学生的成绩。（0≤Ai≤100）

输出

共T行，每行一个整数，代表最少的人数。

输入和输出示例：

　　样例输入：

2
5 60
59 20 30 90 100
5 60
59 20 10 10 100

　　样例输出：

1 2

解题思路：

　　要想改动最少的人来达到新的平均分，就要找出原来分数的最低分，将其改为100，之后进行判定。

代码实现：

package stuSys;
import java.util.Scanner;
public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0;i<T ;i++ ) {
            int n = sc.nextInt();
            int x = sc.nextInt();
            int[] scores = new int[n];
            for (int j =0;j<n ;j++ ) {
                scores[j] = sc.nextInt();
            }
        int answer = updataNum(scores,n,x);
        System.out.println(answer);

        }
    }
    
    //修改成绩的次数
    private static int updataNum(int[] scores,int n, int x){
        int count = 0;
        while(tempAvgScores(scores,n)<x){
            count++;
            int index = findMinScores(scores);
            scores[index] = 100;
        }
        return count;
    }

    //返回平均分
    private static int tempAvgScores(int[] scores,int n){
        int sumResult = 0;
        for (int i=0;i<n ;i++ ) {
            sumResult  +=scores[i];
        }
        return sumResult/n;
    }

    //找出数组中最小数字的下标
    private static int findMinScores(int[] scores){
        int index = 0;
        for(int i=0;i<scores.length;i++){
            if(scores[index]>scores[i])
                index = i;
        }
        return index;
    }
    
}

二、杀手

题目：

　　有n个杀手排成一行，每个杀手都有一个不同的编号（编号为1-n），在每个夜晚，杀手都会行动，如果某个杀手编号大于他右边的杀手的编号，他就会杀死他右边的杀手，杀手的行动是瞬间的，因此一个人可能某一个演完既杀死了别人，又被别人杀死了，例如3,2,1这个顺序，在第一个夜晚2会杀死1，同时3会杀死2.显然易见，一段时间之后，就不会有人杀死或者被杀了，平安夜也就来了，请问在平安夜之前有多少个夜晚？

输入输出说明：

　　输入

第一行是一个整数n（1<=n<=100000）,表示杀手的数量。接下来一行有n个数，是一个1-n的全排列。

　　输出

输出包含一个整数，表示平安夜之前经历个多少了夜晚。

示例：

样例输入
10
10 9 7 8 6 5 3 4 2 1
样例输出
2

解题思路：

从题意中可以理解到，如果要杀手停止杀人，需要满足以下条件之一：

1、只剩下一个人；

2、杀手的序号排列为降序排列；

只有满足这两个条件之一的时候，杀手的序号才不会发生变化，即不会再有人杀或被杀，可以根据这个条件进行判断，如果不满足，就比较前后数的大小，进行相应的remove操作，如果满足，就停止。

代码实现：

import java.util.Scanner;
import java.util.Arraylist;
import java.util.List;
public class Main{
  public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                int n = sc.nextInt();
                List<Integer> listKiller = new ArrayList<Integer>();
                for (int i=0;i<n ;i++) {
                  listKiller.add(sc.nextInt());
                }
                int nightCount = 0;
                int rowSize = listKiller.size();
                while(listKiller.size()>1) {
                    for (int i = listKiller.size()-1; i >= 1; i--) {
                        if (listKiller.get(i)<listKiller.get(i-1)) {
                            listKiller.remove(i);
                        }
                    }
          //判断listKiller大小是否发生变化
                    if(listKiller.size()==rowSize)
                        break;
                    else {
                        rowSize = listKiller.size();
                        nightCount++;
                    }
              }
             System.out.println(nightCount);  
  }
}