0907 科大讯飞双AC Java版

修改成绩

时间限制：C/C++语言 1000MS；其他语言 3000MS 内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

华老师的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

Hint

对于第一组数据，将59改成60即可

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main1 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        ArrayList<Integer> resList = new ArrayList<>();
        for (int i = 0; i < t; i++) {
            int count = 0;
            int n = in.nextInt();
            int X = in.nextInt();
            ArrayList<Integer> list = new ArrayList<>();
            for (int k = 0; k < n; k++) {
                list.add(in.nextInt());
            }
            Collections.sort(list);
            // 都成立的情况下
            if (AverageOfList(list) >=  X) {
                resList.add(count);
                continue;
            }
            // 不成立：开始尝试调整每个list
            for (int c = 0; c < list.size(); c++) {
                list.set(c, 100);
                count++;
                if (AverageOfList(list) >=  X) {
                    resList.add(count);
                    break;
                }
            }
        }
        if(resList.size() == 0){
            return;
        }
        for (int i = 0; i < resList.size(); i++) {
            System.out.println(resList.get(i));
        }
    }
    private static double AverageOfList(ArrayList<Integer> list) {
        int sum = 0;
        for (int i = 0; i < list.size(); i++) {
            sum += list.get(i);
        }
        return sum / (double) list.size();
    }
}

杀手

时间限制：C/C++语言 1000MS；其他语言 3000MS 内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

有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

样例输出

Hint

补充样例
输入样例2
6
1 2 3 4 5 6
输出样例2
0
样例解释：
样例1中杀手的变化为[10 9 7 8 6 5 3 4 2 1]->[10 8 4]->[10]，故答案为2。

说明：所有测试数据均已输出正确结果！ ^_^

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Scanner;
/**
 *
 */
public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(in.nextInt());
        }
        boolean doit = true;
        int count = 0;
        ArrayList<Integer> next = list;
        while (doit) {
            ArrayList<Integer> nextList = new ArrayList<>();
            nextList.add(list.get(0));
            for (int i = 1; i < list.size(); i++) {
                if(list.get(i-1) <= list.get(i)){
                    nextList.add(list.get(i));
                }
            }
            if(nextList.size() == list.size()){
                doit = false;
                break;
            }
            else{
                list = nextList;
                count++;
            }
        }
        System.out.println(count);
    }
}