4.20日阿里笔试

ゝ一世哀愁。 2023-02-11 07:25 15阅读 0赞

# 题目： #

**勇士打怪兽**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]

# 题解： #

**总体思路：**  
从小到大排序，遇到能打过的+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场）][4.20]
2.  [阿里巴巴笔试4/20 实习生][4_20]
3.  [阿里笔试 4月20日 Python][4_20_ Python]
4.  [C/C++代码][C_C]
5.  [阿里笔试4/20场c++][4_20_c]
6.  [阿里 4/20 笔试][4_20 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200522133643344.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200522133743436.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[4.20]: https://www.nowcoder.com/discuss/412997
[4_20]: https://www.nowcoder.com/discuss/412945
[4_20_ Python]: https://www.nowcoder.com/discuss/412884
[C_C]: https://pasteme.cn/33900
[4_20_c]: https://www.nowcoder.com/discuss/412877
[4_20 1]: https://www.nowcoder.com/discuss/412879