已注销

2024-11-29 13:53 已编辑发布于江苏

关注

24届-团子(改编题)-第二套

💻 ACM金牌团队🏅️ | 多次AK大厂笔试｜大厂实习经历

👏 感谢大家的订阅➕ 和喜欢💗 和手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

alt

⚽️ 01.K小姐的植物浇水

问题描述

K小姐有一盆植物，她希望能够在最短的时间内让植物长到至少 $z$ 厘米高。目前植物的高度为 $0$ 厘米。

每天，K小姐可以选择以下两种浇水方式之一：

浇 $x$ 毫升的水，植物高度增加 $x$ 厘米。
浇 $y$ 毫升的水，植物高度增加 $y$ 厘米。需要注意的是，使用第二种浇水方式后，必须至少等待两天才能再次使用该方式。

请你帮助K小姐计算出让植物长到至少 $z$ 厘米高所需的最少天数。

输入格式

输入一行，包含三个整数 $x$ 、 $y$ 和 $z$ ，分别表示两种浇水方式的水量以及目标植物高度。

输出格式

输出一个整数，表示让植物长到至少 $z$ 厘米高所需的最少天数。

样例输入

1 2 10

样例输出

数据范围

$1 \leq x, y, z \leq 10^9$

题解

本题可以使用二分查找的思想来解决。我们可以二分枚举所需的天数 $d$ ，判断在 $d$ 天内是否能够让植物长到至少 $z$ 厘米高。

对于每个枚举的天数 $d$ ，我们可以计算出在这 $d$ 天内使用第二种浇水方式的最大次数为 $\lfloor \frac{d}{3} \rfloor$ 。然后，我们可以计算出在这 $d$ 天内，使用第一种浇水方式的次数为 $d - \lfloor \frac{d}{3} \rfloor$ 。

因此，在 $d$ 天内，植物的最大高度为：

$height = x \times (d - \lfloor \frac{d}{3} \rfloor) + y \times \lfloor \frac{d}{3} \rfloor$

如果 $height \geq z$ ，说明在 $d$ 天内可以让植物长到至少 $z$ 厘米高，我们可以缩小二分的范围；否则，我们需要增大二分的范围。

通过二分查找，我们可以找到最小的满足条件的天数。

时间复杂度： $O(\log z)$ ，其中 $z$ 为目标植物高度。空间复杂度： $O(1)$ 。

参考代码

Python

def is_feasible(d, x, y, z):
    num = (d // 3) * y + d * x
    if d % 3 != 0:
        num += y
    return num >= z

x, y, z = map(int, input().split())
left, right = 0, z // x + 1
while left < right:
    mid = (left + right) // 2
    if is_feasible(mid, x, y, z):
        right = mid
    else:
        left = mid + 1
print(right)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        int z = scanner.nextInt();
        int left = 0, right = z / x + 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (isFeasible(mid, x, y, z)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(right);
    }

    public static boolean isFeasible(int d, int x, int y, int z) {
        long num = (d / 3) * y + d * x;
        if (d % 3 != 0) {
            num += y;
        }
        return num >= z;
    }
}

#include <iostream>
using namespace std;

int x, y, z;

bool isFeasible(int d) {
    long long int num = (d / 3) * y + d * x;
    if (d % 3) {
        num += y;
    }
    return num >= z;
}

int main() {
    cin >> x >> y >> z;
    int left = 0, right = z / x + 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (isFeasible(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    cout << right;
    return 0;
}

🥬 02.LYA 的公寓租金分摊

问题描述

LYA 是一位年轻有为的创业者,她在城市里拥有 $n$ 栋公寓楼。每栋公寓楼都有若干名租户入住,LYA 自己也在每栋楼里保留了一个住处。现在,是每个月向租户们收取租金的时候了。

对于第 $i$ 栋公寓楼,共有 $k_i$ 名租户(包括 LYA 自己),月租总金额为 $c_i$ 。为了公平起见,LYA 决定将总租金 $c_i$ 平均分摊给所有租户(包括她自己),每人需支付 $\lceil \frac{c_i}{k_i} \rceil$ 的金额。这里, $\lceil x \rceil$ 表示对实数 $x$ 向上取整。

现在,LYA 希望你能帮她计算每位租户需要支付的租金金额。

输入格式

第一行包含两个正整数 $n$ 和 $m$ ,分别表示 LYA 拥有的公寓楼数量和城市中租户的总数。 $(1 < n, m \le 10^5)$

接下来有 $2n$ 行,每两行描述一栋公寓楼的信息:

第一行包含两个整数 $k_i$ 和 $c_i$ ,分别表示该公寓楼的租户总数(包括 LYA)和月租总金额。 $(2 \le k_i \le m+1, 1 \le c_i \le 10^9)$
第二行包含 $k_i-1$ 个整数,表示每位租户(不包括 LYA)的编号。租户编号在 $1$ 到 $m$ 之间。

输出格式

输出包含 $m$ 个整数,第 $i$ 个整数表示编号为 $i$ 的租户需要支付的租金金额。

样例输入

样例输出

7 7 3

数据范围

$1 < n, m \le 10^5$
$2 \le k_i \le m+1$
$1 \le c_i \le 10^9$
租户编号在 $1$ 到 $m$ 之间

题解

本题要求我们计算每位租户需要支付的租金金额。由于 LYA 自己也算作一名租户,因此每栋公寓楼的实际租户数为输入的 $k_i-1$ 。

我们可以先创建一个长度为 $m$ 的数组 rent,用于存储每位租户的租金金额,初始值都为 $0$ 。

然后,对于每栋公寓楼,我们计算出每位租户需要支付的租金金额 $\lceil \frac{c_i}{k_i} \rceil$ ,然后将其累加到对应租户的租金金额上。

最后,我们将 rent 数组中的租金金额按顺序输出即可。

时间复杂度为 $O(n \times \bar{k})$ ,其中 $\bar{k}$ 为每栋公寓楼的平均租户数。空间复杂度为 $O(m)$ 。

参考代码

Python

n, m = map(int, input().split())
rent = [0] * m

for _ in range(n):
    k, c = map(int, input().split())
    cost = (c + k - 1) // k
    
    for x in map(int, input().split()):
        rent[x - 1] += cost

print(*rent)

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        long[] rent = new long[m];
        for (int i = 0; i < n; ++i) {
            String[] kc = br.readLine().split(" ");
            int k = Integer.parseInt(kc[0]);
            int c = Integer.parseInt(kc[1]);
            long cost = (c + k - 1) / k;
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                int x = Integer.parseInt(st.nextToken());
                rent[x - 1] += cost;
            }
        }
        
        System.out.println(Arrays.stream(rent).mapToObj(Long::toString).collect(Collectors.joining(" ")));
    }
}

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    long long rent[m] = {0};
    
    for (int i = 0; i < n; ++i) {
        int k, c;
        cin >> k >> c;
        long long cost = (c + k - 1) / k;
        
        for (int j = 0; j < k - 1; ++j) {
            int x;
            cin >> x;
            rent[x - 1] += cost;
        }
    }
    
    for (int i = 0; i < m; ++i) {
        cout << rent[i] << (i == m - 1 ? "\n" : " ");
    }
    
    return 0;
}