2023 顺丰笔试题 顺丰科技笔试 0914
笔试时间:2023年9月14日 秋招
第一题
题目:巧克力
小丽明天要出去和同学春游。她准备带上总面积恰好为n 的巧克力板(简化起见将巧克力板视为平面图形,忽略它的厚度,只考虑面积)去和同学们一起分享。出于美感的考虑,小丽希望她带上的巧克力板都是边长为整教的正方形,另一方面出于便携性考虑,小丽希望这些巧克力板的周长之和尽可能小。请你帮小丽找出可 能的最小周长!换句话说,小丽需要你帮忙找出k个小正方形巧克力板,边长分别为a2,a2,...,ak,使得其面积之和,即∑[1<=i<=k]ai^2,恰好为要求的总面积为n;同时使得总周长,∑[1<=i<=k]4*ai最小。
输入描述
一行,1个整数n,表示小丽希望带上的巧克力板总面积。
1<=n<=50000
输出描述
输出一行一个整数表示可能的最小周长
样例输入
11
样例输出
20
说明
我们带上三块边长分别为3、1、1的正方形巧克力板,总面积为3^2+1^2+1^2=11,此时周长为4*(3+1+1)=20。可以证明没有周长更小的方案。
参考题解
dp数组。
Java:[此代码未进行大量数据的测试,仅供参考]
import java.util.Scanner; import java.util.Arrays; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] dp = new int[50005]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = i * i; j <= n; j++) { dp[j] = Math.min(dp[j], dp[j - i * i] + i); } } System.out.println(dp[n] << 2); } }
Python:[此代码未进行大量数据的测试,仅供参考]
n = int(input()) dp = [float('inf')] * 50005 dp[0] = 0 for i in range(1, n + 1): for j in range(i * i, n + 1): dp[j] = min(dp[j], dp[j - i * i] + i) print(dp[n] <
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2023 秋招笔试题汇总解析 文章被收录于专栏
2023秋招各大笔试题汇总,c++,java,python多种语言分析,解答。