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

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

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

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

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

☀️ 01.汉堡王优惠活动

问题描述

K小姐最喜欢到多哆村的金哆炸鸡店吃汉堡，每个汉堡原价 元。为了回馈老顾客，炸鸡店开展了拼团活动：每找到一个朋友一起购买，就可以减少 元，但价格最低只能降到 元（否则就要亏本啦）。

现在 K小姐 手上有 元钱，同时有 个朋友也想吃汉堡。K小姐 想知道自己最多能买多少个汉堡，以及在买最多汉堡的情况下最少要花多少钱。

输入格式

第一行包含一个正整数 ，表示测试用例的数量。

接下来 行，每行包含两个正整数 和 ，分别表示 K小姐 的钱数以及一起购买汉堡的朋友数量。

输出格式

对于每组测试用例，输出一行，包含两个整数，分别表示 K小姐 能购买的最多汉堡数量，以及购买最多汉堡时最少需要花的钱数。

样例输入

3
100 0
20 18
5 3

样例输出

10 100
3 15
0 0

数据范围

题解

本题的关键是判断能够凑成多少个优惠价 元的汉堡。

首先，我们可以计算出朋友数量可以凑成的 元汉堡个数 ，以及凑成这些汉堡后剩余的朋友数量 。

如果 个 元汉堡的总价格超过了 K小姐 的钱数 ，那么最多只能买 个汉堡，花费 元。

否则，在买完 个 元汉堡后，如果剩下的钱加上剩余的朋友数量可以再凑成一个 元的汉堡，那么就再买一个，并将剩下的钱按照 元一个汉堡的价格继续购买。如果不能凑成 元的汉堡，那么最多就只能买 个汉堡，花费 元。

参考代码

• Python

T = int(input())

def solve():
    n, m = map(int, input().split())
    t = m // 5  # 5元汉堡个数
    m %= 5
    
    if t * 5 > n:
        print(n // 5, (n // 5) * 5)
    else:
        n -= t * 5
        if n >= 10 - m:
            n -= (10 - m)
            print(t + 1 + (n // 10), t * 5 + 10 - m + (n // 10) * 10)
        else:
            print(t, t * 5)

for _ in range(T):
    solve()

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            solve(sc);
        }
    }
    
    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int t = m / 5;  // 5元汉堡个数
        m %= 5;
        
        if (t * 5 > n) {
            System.out.println((n / 5) + " " + ((n / 5) * 5));
        } else {
            n -= t * 5;
            if (n >= 10 - m) {
                n -= (10 - m);
                System.out.println((t + 1 + (n / 10)) + " " + (t * 5 + 10 - m + (n / 10) * 10));
            } else {
                System.out.println(t + " " + (t * 5));
            }
        }
    }
}

• Cpp

#include <iostream>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    int t = m / 5;  // 5元汉堡个数
    m %= 5;
    
    if (t * 5 > n) {
        cout << n / 5 << " " << (n / 5) * 5 << endl;
    } else {
        n -= t * 5;
        if (n >= 10 - m) {
            n -= (10 - m);
            cout << t + 1 + (n / 10) << " " << t * 5 + 10 - m + (n / 10) * 10 << endl;
        } else {
            cout << t << " " << t * 5 << endl;
        }
    }
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        solve();
    }
    
    return 0;
}

🌤 02.二进制字符串的十进制值

题目描述

K小姐特别喜欢二进制字符串。有一天，博学的 A 先生在迁居时遇到了 K 小姐，他准备考考她。

A先生每次会给K小姐一个长度为 的二进制字符串 。他定义了一种新的子串 ，作为十进制表示形式为 的数字（可能有前导零）。A 先生定义字符串的十进制值 为所有有效的 的总和，换句话说：

例如，对于字符串 ：

因此，。

A 先生允许 K 小姐每次可以交换字符串的任意两个相邻元素，最多可以进行 次操作。他问 K 小姐，在进行操作后，字符串的十进制值最小是多少。K 小姐喜欢分享，于是她邀请你一起解决这个问题。

输入格式

第一行包含一个整数 ，表示测试用例的数量。

对于每组测试用例：

• 第一行包含两个整数 和 ，分别表示字符串的长度和允许的最大操作数。
• 第二行包含一个长度为 ，仅由 和 组成的二进制字符串 。

输出格式

对于每组测试用例，分别输出一行，每行一个整数，表示在最多可以进行 次操作后字符串的最小十进制值。

样例输入

2
5 0
10100
7 2
0010100

样例输出

21
12

数据范围

题解

观察可以发现中间部分的 '1' 对答案的贡献不变，只有首尾的 '1' 贡献会不一样，主要策略是尽量将 '1' 移动到字符串的尾部，从而减少由 '1' 产生的高权重。首先尝试将最后一个 '1' 尽可能右移，如果剩余操作数还允许，再将第一个 '1' 尽可能左移。这样可以最大程度减少 '1' 的有效出现次数，从而降低总和。

参考代码

• Python

def solve():
    n, k = map(int, input().split())
    s = input().strip()
    idx0 = s.find('1')
    idx1 = s.rfind('1')

    # Function to perform operation 0
    def op0(idx0):
        nonlocal k
        if idx0 == -1:
            return
        while k > 0 and idx0 > 0:
            s_lst = list(s)
            s_lst[idx0], s_lst[idx0 - 1] = s_lst[idx0 - 1], s_lst[idx0]
            s = ''.join(s_lst)
            k -= 1
            idx0 -= 1

    # Function to perform operation 1
    def op1(idx1):
        nonlocal k
        if idx1 == -1:
            return
        while k > 0 and idx1 < n - 1:
            s_lst = list(s)
            s_lst[idx1], s_lst[idx1 + 1] = s_lst[idx1 + 1], s_lst[idx1]
            s = ''.join(s_lst)
            k -= 1
            idx1 += 1

    if n - idx1 - 1 <= k:
        op1(idx1)
    op0(idx0)
    res = 0
    for i in range(n - 1):
        res += int(s[i:i + 2])
    print(res)

T = int(input())
for _ in range(T):
    solve()

• Java

import java.util.Scanner;

public class Main {

    static void solve() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        String s = scanner.next();
        int idx0 = s.indexOf('1');
        int idx1 = s.lastIndexOf('1');

        // 操作0：将'1'向左移动
        Runnable op0 = () -> {
            if (idx0 == -1) return;
            while (k > 0 && idx0 > 0) {
                char temp = s.charAt(idx0);
                s.setCharAt(idx0, s.charAt(idx0 - 1));
                s.setCharAt(idx0 - 1, temp);
                k--;
                idx0--;
            }
        };

        // 操作1：将'