京东0923秋招笔试

2023秋招

笔试真题

发布日期: 2023-09-28

更新日期: 2024-03-09

文章字数: 1.5k

阅读时长: 6 分

阅读次数:

京东0923秋招笔试

最近挺忙的，一方面是学业方面的实验任务；另一方面是实习任务加重了，Leader休年假，在放假之前布置了很多任务。这两天干了挺多的。现在接着看看秋招笔记，把真题做一下。

0923.T1

1. 题目说明

小红需要n个不同的魔法药剂，她可以从商店以ai的价格购买第i种红色版本魔法药剂，也可以用两种其他的红色版本药剂配置蓝色版本小红想知道，她最少需要花多少钱才能得到1到n个不同的魔法药剂，蓝色或者红色都可以。

输入描述

第一行输入一个整数n，表示魔法药剂数量。

第二行输入n个整数ai，表示第i种红色版本魔法药剂的价格。

接下来n行，每行两个整数bi和ci，表示用第 bi 种和第 ci 种红色版本魔法药剂配置第 i 种蓝色版本魔法药剂。

1<= n <=1e5

1<= ai <=1e4

1<= bi,ci <= n

输出描述

输出一个整数，表示最少需要花多少钱才能得到1到n个不同的魔法药剂，蓝色或者红色都可以。

示例1

输入

5
2 4 10 1 3

输出

说明

红色药剂的价格分别为[2, 4, 10, 1, 3]。

蓝色药剂的价格分别为[14, 4, 6, 7, 3]。这里注意蓝色药剂合成用到的红色试剂的种类，给定的顺序即可

配置第三种蓝色药剂，其他都购买红色药剂花费 16

2. 解答分析

其中，n表示魔法药剂数量，ai表示第i种红色版本魔法药剂的价格，bi和ci表示用第bi种和第ci种红色版本魔法药剂配置第i种蓝色版本魔法药剂。在运行代码后，它将输出最少花费的结果。
思路是简单的模拟，哪种做法便宜用哪个。
处理思路是使用贪心算法，首先将红色药剂价格和蓝色药剂价格分别存储在两个List中。接着，遍历每一个蓝色药剂，计算用哪两种红色药剂来组合可以得到最小价格，将该价格存储在price List中。最后，遍历price List，将各个价格累加起来，即为最终的答案。

3. 具体代码

import java.util.*;

public class title1 {
        public static void main(String[] args) {
            Scanner scanner=new Scanner(System.in);
            int n = scanner.nextInt();
            List<Long> red = new ArrayList<>();
            List<Long> price = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                red.add(scanner.nextLong());
                price.add(1000005L);
            }

            List<List<Long>> blue = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                List<Long> temp = new ArrayList<>();
                temp.add(scanner.nextLong());
                temp.add(scanner.nextLong());
                temp.set(0, temp.get(0) - 1);
                temp.set(1, temp.get(1) - 1);
                blue.add(temp);
            }
            for (int i = 0; i < n; i++) {
                long minPrice = Math.min(red.get(i), red.get(blue.get(i).get(0).intValue()) + red.get(blue.get(i).get(1).intValue()));
                price.set(i, minPrice);
            }

            long ans = 0;
            for (long x : price) {
                ans += x;
            }

            System.out.println(ans);
        }
}

复杂度分析：
- 时间复杂度： $O(n)$
- 空间复杂度： $O(n)$
  
  因为需要用List来存储红色药剂价格、蓝色药剂价格和最小价格。但是由于n的范围比较小，所以空间复杂度不会是问题。

0923.T2

1. 题目说明

小红有一个长度为n的数组。如果存在一个长度为3的子数组，使得a_i <= a_i+1 <= a_i+2，那么这个数组就是有趣的。每次操作可以修改数组的一个值，请问最少需要几次操作才能使得这个数组变得不有趣

输入描述

第一行输入一个整数n，表示数组的长度。第二行输入几个整数a1, a2，···，an，表示数组的初始值。

1<= n <=1e5 1<= ai <= 1e9

输出描述

输出一个整数，表示答案

示例

输入

5
6 2 4 5 1

输出

2. 解答分析

贪心+找规律
首先找出所有连续的有趣子数组，记录其长度；
对于递增子数组，可以通过将其中间的数改为一个较大值进行破坏，可以证明破坏边缘不如破坏中间；

长度为3，需要1次；

长度为4，需要1次；

长度为5，相当于破坏1次+长度为3；

长度为6，相当于破坏一次+长度为4；

找规律为破坏次数 = （(连续递增子数组长度 - 1 ) / 2），累加就行了

3. 具体代码

import java.util.ArrayList;
import java.util.Scanner;
import java.util.List;

public class title2 {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        List<Integer> arr=new ArrayList<>();
        for(int i=0;i<n;i++){
            arr.add(in.nextInt());
        }
        List<Integer>nums=new ArrayList<>();
        int len=1,ans=0;
        for(int i=1;i<n;i++) {//从第二个元素开始迭代
            if (arr.get(i) >= arr.get(i - 1)) {
                len++;//记录最长的子数组的长度
            } else {//遇到非递增子数组时，判断此时的子数组的长度大于3即可
                if (len >= 3) {
                    nums.add(len);
                    len = 0;
                }
            }
        }
            if(len>=3){
                nums.add(len);//检查最后的序列
            }
            for(int x:nums){//遍历每个满足的子数组的长度，从中间的元素开始进行替换
                ans+=(x-1)/2;//3个改一个，4个改中间1个，5个改1个+3个的情况...
            }
        System.out.println(ans);
        in.close();
    }
}