算法编程（美团）

1.某比赛已经进入了淘汰赛阶段,已知共有n名选手参与了此阶段比赛，他们的得分分别是a_1,a_2….a_n,小美作为比赛的裁判希望设定一个分数线m，使得所有分数大于m的选手晋级，其他人淘汰。

但是为了保护粉丝脆弱的心脏，小美希望晋级和淘汰的人数均在[x,y]之间。

显然这个m有可能是不存在的，也有可能存在多个m，如果不存在，请你输出-1，如果存在多个，请你输出符合条件的最低的分数线。

数据范围：1≤n≤50000 1\le n \le 50000\ 1≤n≤50000 ，1≤x≤y≤n 1 \le x \le y \le n\ 1≤x≤y≤n

进阶：时间复杂度O(nlogn) O(nlogn)\ O(nlogn) ，空间复杂度O(n) O(n)\ O(n)

输入描述:

输入第一行仅包含三个正整数n,x,y，分别表示参赛的人数和晋级淘汰人数区间。(1<=n<=50000,1<=x,y<=n)

输入第二行包含n个整数，中间用空格隔开，表示从1号选手到n号选手的成绩。(1<=|a_i|<=1000)

输出描述:

输出仅包含一个整数，如果不存在这样的m，则输出-1，否则输出符合条件的最小的值。

示例1

输入

6 2 3

1 2 3 4 5 6

输出

3

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 x = in.nextInt();
        int y = in.nextInt();
        int[] score = new int[n];
        for (int i = 0; i < n; i++) {
            score[i] = in.nextInt();
        }
        /**
         * 符合条件的最低分数线 -> 过线的人多 -> 使用人数限制最大值 y作为过线人数 -> 判断剩下的人数 是否在[x,y]区间 ->
         *      如果在 直接返回
         *      如果不在
         *          如果人数少于x 则直接找到分数最低的第x个人即可
         *          如果人数大于y 则证明找不到一个分数线满足条件
         */
        // 对成绩排序
        Arrays.sort(score);
        // 没过线的人数
        int notOk = n - y;
        if (notOk > y) {
            System.out.println(-1);
        } else if (notOk >= x && notOk <= y) {
            System.out.println(score[n - y - 1]);
        } else {
            System.out.println(score[x - 1]);
        }
    }
}

2.正则序列

我们称一个长度为n的序列为正则序列，当且仅当该序列是一个由1~n组成的排列，即该序列由n个正整数组成，取值在[1,n]范围，且不存在重复的数，同时正则序列不要求排序

有一天小团得到了一个长度为n的任意序列s，他需要在有限次操作内，将这个序列变成一个正则序列，每次操作他可以任选序列中的一个数字，并将该数字加一或者减一。

请问他最少用多少次操作可以把这个序列变成正则序列？

数据范围：1\le n \le 20000\1≤n≤20000 ，0\le abs(s_i) \le 10000 \0≤abs(si)≤10000

进阶：时间复杂度O(n)\O(n) ，空间复杂度O(n)\O(n)

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

输入第一行仅包含一个正整数n，表示任意序列的长度。(1<=n<=20000)

输入第二行包含n个整数，表示给出的序列，每个数的绝对值都小于10000。

输出描述：

输出仅包含一个整数，表示最少的操作数量。

示例1

输入例子：

5

-1 2 3 10 100

输出例子：

103

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        int ans = 0;
        for(int i = 0;i < n;i++)
            nums[i] = sc.nextInt();
        Arrays.sort(nums);
        for(int i = 0;i < n;i++){
            ans += Math.abs(i + 1 - nums[i]);
        }
        System.out.println(ans);
    }
}