滴滴笔试题

2025.08.26

P3476. 第1题-你的一半归我了

题目内容

给定正整数 n 和一个大小为 n 的数组。小种可以对这个数组执行若干次以下操作:选择一个下标$i$令 $x=[\frac{a_i}{2}]$ (即向下取整)，令$a_1=a_1+x$,$a_i=a_i−x$。

小钟需要求出最少的操作次数使得 $a_1$成为数组中最大的元素，即对于任意的$ i(2<=i<=n) $满足$ a_i<a_1 $。题目保证给定数据一定存在答案。

请你计算出最少的操作次数是多少。

输入描述

输入包括多组测试数据。

输入第一行包括一个正整数 T(1<=T<=100)T(1<=T<=100) ，表示测试数据的组数。

每组测试数据的第一行有一个整数 n(1<=n<=105)n(1<=n<=105) ，表示数组的大小;

接下来的一行有 nn 个整数 a1,a2,…,an(2<=ai<=109)a1,a2,…,a**n(2<=a**i<=109) ，表示题目给定的数组。

保证每个测试点的所有测试数据的 nn 的和不超过 2∗1052∗105 。

输出描述

对于每组测试数据，输出一个正整数表示使得 aia**i，成为最大元素的最少的操作次数。

答案

采用贪心策略，每次都取剩余元素中最大的那一个，可以实现最小步数。维护剩余元素中的最大值可以使用最大（最小堆）。

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int len = Integer.parseInt(sc.nextLine());
        for(int i = 0 ; i < len ; i ++){
            int res = 0;
            int n = Integer.parseInt(sc.nextLine());
            String[] s = sc.nextLine().split(" ");
            long a = Long.parseLong(s[0]);
            PriorityQueue<Long> p = new PriorityQueue<>(
                Comparator.reverseOrder()
            );
            for(int j = 1 ; j < n ; j++){
                p.offer(Long.parseLong(s[j]));
            }
            long peek = p.peek();
            while( a <= peek){
                peek = p.poll();
                long x = peek / 2;
                a = a + x;
                peek = peek - x;
                p.add(peek);
                peek = p.peek();
                res ++;
            }
            System.out.println(res);
        }
    }
}

P3477. 第2题-寻宝之旅

题目描述

有一座巨大的宫殿，可以被视为由 $n$ 行 $n$ 列房间组成，从上到下分别为第 $1,2,…,n$ 行，从左到右分别为第 $1,2,…,n$ 列。第 $i$ 行第 $j$ 列房间内有价值为 $a_{i,j}$ 的宝藏。

每个房间都有一扇通往下一行同一列的常开的门，即从第 $i$ 行第 $j$ 列房间能移动到第 $i+1$ 行第 $j$ 列房间，但是如果选择带走房间内的宝藏，则该侧门会关闭。特别地，第 $n$ 行的所有房间的通往下一行同一列的门都通往宫殿外。

除此之外，每个房间都有通往同一行下一列的门，即第 $i$ 行第 $j$ 列房间有一扇通往第 $i$ 行第 $j+1$ 列房间的门，该门不常开，但是如果选择带走房间内的宝藏，则该侧门会打开。特别地，第 $n$ 列的所有房间的通往同一行下一列房间的门都通往宫殿外。

小钟从第一行第一列房间出发，他想知道在离开宫殿前他最多能够带走多少价值的宝藏。请你帮忙计算答案。

输入描述

输入包括多组测试数据。

输入第一行包括一个正整数 $T(1 \leq T \leq 10)$，表示测试数据的组数。

每组测试数据的第一行有一个整数 $n(1 \leq n \leq 500)$，表示宫殿由 $n$ 行 $n$ 列房间组成；

接下来的 $n$ 行第 $i$ 行有 $n$ 个整数 $a_{i,1}, a_{i,2}, …, a_{i,n}(0 \leq a_{i,j} \leq 10^5)$，依次表示第 $i$ 行第 $1,2,…,n$ 列房间内宝藏的价值大小。

保证每个测试点的所有测试数据的 $n^2$ 的和不超过 $2.5 \times 10^5$。

输出描述

对于每组测试数据，输出一个正整数表示小钟离开宫殿前最多能够带走多少价值的宝藏。

答案

构造二维dp数组，定义$dp[i][j]$为在$i,j$时所能得到的最大宝藏价值之和。转移方程为：
$$
dp[i][j] = Max(dp[j-1][k], dp[j][k-1] + num[j][k-1]);
$$

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = Integer.parseInt(sc.nextLine());
        for(int i = 0 ; i < T ; i ++){
            int n = Integer.parseInt(sc.nextLine());
            int[][] num = new int[n][n];
            for(int j = 0 ; j < n ; j++){
                String[] s = sc.nextLine().split(" ");
                for(int k = 0 ; k < n ; k ++){
                    num[j][k] = Integer.parseInt(s[k]);
                }
            }
            int[][] dp = new int[n][n];
            dp[0][0] = 0;
            for(int p = 1 ; p < n ; p ++){
                 dp[p][0] = dp[p-1][0];
                 dp[0][p] = dp[0][p-1] + num[0][p-1];
            }
            for(int j = 1 ; j < n ; j ++){
                for(int k = 1 ; k <n ;k++){
                    dp[j][k] = Math.max(dp[j-1][k], dp[j][k-1] + num[j][k-1]);
                }
            }
            int res = 0;
            for(int r = 0 ; r < n ; r++){
                res = Math.max(dp[n-1][r], res);
                res = Math.max(dp[r][n-1] + num[r][n-1] ,res);
            }
            System.out.println(res);
        }
    }
}