2023 拼多多笔试题 0910

笔试时间:2023年9月10日 秋招

第一题

题目:文数组

多多最近在研究一种由n个数字构成的特殊数组X ={x1,x2,x3.....xn},这个数组有2个特点:

1、X数组是严格递增的,也就是x1 < t2 <···< xn;

2、X数组的相邻数字间做差值,得到新数组Y是严格递减的。换话说,用yi = xi+1 - xi表示相数字间差值,则新数组Y ={y1,y2,...,yn}满足: y1 > y2 >...>Yn-1;

现在,假设有数字n、数组的第一个数字的值a=x1以及数组最后一个数字的值b =xn的情况下,多多想知道能不能到找到任意1个这样的特殊数组,同时满足上面两个条件。

输入描述

第一行,一个整数T,表示测试用例的组数(1 <T<3000);

接下来每组测试用例包含一行数据,由3个数字构成分别是: n,a,b( 1<= n <= 400,1<=a <=b<= 1000),分别表示: 数组的长度、第个数字的值、最后一个数字的值。

输出描述

每组测试用例,输出一行:YES 或者NO表示: 是否存在任意1个这样的数组。

样例输入

3

3 1 5

5 1 5

5 1 100

样例输出

YES

NO

YES

提示

共有3组测试用例,对于第1组用例,可以找到数组:[1,4.5] 满足数组本身是严格递增的,数组相邻数字之间的差值[3,1] 是严格递减的,所以输出:YES;

对于第2组用例,严格递增的数组是:[1,2,3,4,5],但是数组相邻数字之间差值构成的数组[1,1,1,1] 不满足严格递减,所以输出:NO;

对于第3组用例,可以找到数组:[1,40,70,90,100],满足数组本身严格递增,数组相邻数字之间的差值[39,30,20,10]满足严格递减,所以输出: YES。

参考题解

通过构造数组Y,从而构造数组X,假设Y=[n-1,n-2,...1],则Xn至少等于a + n(n-1)/2。验证a + n(n-1)/2 <=b 即可。

Java:[此代码未进行大量数据的测试,仅供参考]

import java.util.Scanner;

class TestCases {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T-- > 0) {
            int n = scanner.nextInt();
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            System.out.println(a + n * (n - 1) / 2 <= b ? "YES" : "NO");
        }
    }
}

Python:[此代码未进行大量数据的测试,仅供参考]

def solve():
    n, a, b = map(int, input().split())
    print("YES" if a + n * (n - 1) // 2 <= b else "NO")

if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        solve()

第二题

题目:数字匹配

多多君从小到大都没有谈过恋爱,因此他希望大家都能成双入对,包括数字。现在他有一串数字,他希望其中的数字能两两匹配。能够两两匹配的数字满足如下要求:

1、他们之间差的绝对值大于等于一个特定值;

2、他们没有出现在其他数字对中,即每个数字只能被匹配一次或零次。

现在,多多君希望能知道,给定一串数字,最多可以匹配成功多少对数字对。

输入描述

第一行,2个整数N、M,分别表示数字的个数和要求数字间的差异值(1 < N < 2000000, 0 <M<10)

接下来一行,由N个整数构成,分别表示第i个数字Xi。(0 <=Xi<=10^9)

输出描述

一个数字,表示在给定的数字中,能匹配的最多数字对个数。

样例输入

示例一:

4 2

1 3 3 7

示例二:

5 5

10 9 5 8 7

样例输出

示例一:

2

提示:可以匹配最多2个数字对(1,3)和(3,7)。

示例二:

1

提示:可以匹配最多1个数字对(5.10),其余数字对都不满足差的绝对值大于等于5。

参考题解

二分法。

Java:[此代码未进行大量数据的测试,仅供参考]

import java.util.Arrays;
import java.util.Scanner;

class BinarySearchProblem {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = 2000004;
        int[] a = new int[M];
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }

        Arrays.sort(a, 1, n + 1);
        int l = 0, r = n / 2;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (ok(a, n, m, mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        System.out.println(l);
    }

    static boolean ok(int[] a, int n, int m, int k) {
        for (int i = 1; i <= k; i++) {
            if (a[n - k + i] - a[i] < m) {
                return false;
            }
        }
        return true;
    }
}

Python:[此代码未进行大量数据的测试,仅供参考]

def ok(a, n, m, k):
    for i in range(1

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

2023 秋招笔试题汇总解析 文章被收录于专栏

2023秋招各大笔试题汇总,c++,java,python多种语言分析,解答。

全部评论
是内推吗
点赞 回复 分享
发布于 2023-09-23 13:45 广东
好简单的题
点赞 回复 分享
发布于 2023-12-26 16:57 北京
这个文数组要求数组值一定是整数对吗?允许小数的话第二个也对呀
点赞 回复 分享
发布于 03-23 11:00 北京

相关推荐

不愿透露姓名的神秘牛友
11-03 11:17
点赞 评论 收藏
分享
某家大公司 项目经理 基础工资在1w左右,另一个是月8k包吃住
点赞 评论 收藏
分享
1 7 评论
分享
牛客网
牛客企业服务