大厂秋招真题【贪心】顺丰20230914秋招T2-巧克力

顺丰20230914秋招T1-巧克力

题目描述与示例

题目描述

小丽明天要出去和同学春游。她准备带上总面积恰好为n的巧克力板(简化起见将巧克力板视为平面图形，忽略它的厚度,只考虑面积)去和同学们一起分享。

出于美感的考虑,小丽希望她带上的巧克力板都是边长为整数的正方形;另一方面出于便携性考虑，小丽希望这些巧克力板的周长之和尽可能小,请你帮小丽找出可能的最小周长！

换句话说,小丽需要你帮忙找出k个小正方形巧克力板，边长分别为a1, a2, ..., ak,使得其面积之和,即$$\sum _{i=1}^k{a}_i^2$$,恰好为要求的总面积为n；同时，使得总周长,即$$\sum _{i=1}^{k}4\ast a_i$$最小

输入描述

一行，1个整数n，表示小丽希望带上的巧克力板总面积

1 <= n <= 50000
1

输出描述

输出一行一个整数表示可能的最小周长。

示例

输入

11
1

输出

20
1

解题思路

首先可以确定的是对于任意的n，一定可以表示成为若干数字的平方和，因为一种保底的策略是n个1的平方相加。

接下来我们考虑为了能够让$$\sum _{i=1}^{k}4a_i$$最小，而$$\sum _{i=1}^k{a}_i^2$$等于n。一种显然的贪心策略是我们优先塞大的ai，

这是较大的ai值的平方会比较小的ai值的平方更快地减小n的值，从而最终使得a1 + a2 + ... + ak最小。

代码

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        for (int i = n; i >= 1; --i) {
            while(i * i <= n) {
                n -= i * i;
                ans += i;
            }
        }
        System.out.println(4 * ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

C++

#include 

using namespace std;

int main() {
        int n;
        cin >> n;
        int ans = 0;

        for (int i = n; i >= 1; --i) {
                while(i * i <= n) {
                        n -= i * i;
                        ans += i;
                }
        }
        cout << 4 * ans << endl;
        return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多