4.20日阿里笔试

题目：

勇士打怪兽

题解：

总体思路：
从小到大排序，遇到能打过的+1，遇到打不过的升级，记录金币的最大值。

具体思路：

1. 先对所有怪兽的能力值数组进行排序，从弱的开始打；
2. 遍历排序后的所有怪兽，如果能力值够打，就打完拿 1 金币；
3. 如果当前金币+能力值够打，就打完拿 1 金币（金币和能力值进行更新）；
4. 用一个值记录最大金币，每次用金币补贴之前先更新最大值；
5. 打印最大金币数；

代码：

import java.util.*;

public class Main_1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt())
        {
            int a = sc.nextInt(); // 勇士能力值 a
            int n = sc.nextInt(); // 怪兽个数 n
            int index = 0; // 数组下标 index
            int count = 0; // 金币数 count
            int x[] = new int[n];
            for(int i = 0; i < n; i++)
            {
                x[i] = sc.nextInt(); // n个数，分别代表怪兽的能力值 x[i]
            }
            Arrays.sort(x); // 先对所有怪兽的能力值数组进行排序，从弱的开始打
            for(int i = 0; i < n; i++)
            {
                if(a >= x[i]) // 遍历排序后的所有怪兽，如果能力值够打，就打完拿 1 金币
                {
                    count++;
                    index = i;
                }
            }
            int cnt = count; // 金币数 cnt
            int max = count; // 最大金币数 max
            int res; // 每个怪兽的能力值 x[i] - 勇士能力值 a == res(差值)
            for(int i = index + 1; i < n; i++)
            {
                if(cnt + n < x[i])
                {
                    break;
                }
                else // 如果当前金币+能力值够打，就打完拿 1 金币(金币和能力值进行更新)
                {
                    res = x[i] - a;
                    a = a + res;
                    cnt = cnt - res;
                }
                if(a >= x[i])
                {
                    cnt++;
                }
                if(cnt > max) // 用一个值记录最大金币，每次用金币补贴之前先更新最大值
                {
                    max = cnt;
                }
            }
            System.out.println(max); // 打印最大金币数
        }             
    }
}

// 输入：
// 1 3
// 2 2 1
// 输出：
// 2

参考：

1. 阿里笔试记录（4.20场）
2. 阿里巴巴笔试4/20 实习生
3. 阿里笔试 4月20日 Python
4. C/C++代码
5. 阿里笔试4/20场c++
6. 阿里 4/20 笔试