美团嵌入式软件实习笔试编程题

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《软件开发笔试汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

1.小美点外卖

小美是美团外卖的忠实用户，她经常去美团外卖 app 上面点外卖，因为会员红包的性价比太高啦！

现在小美点了若干道菜，她希望你计算一个订单的总价。你能帮帮她吗？

输入描述

第一行输入一个正整数n，代表菜品总数。

第二行输入n个正整数ai，代表每道菜的价格。

第三行输入两个正整数x和y，x代表满减的价格，y代表红包的价格。

1<=n<=10^5

1<=x,y,ai<=10^9

保证所有的和大于，保证会用到满减

输出描述

一个正整数，代表小美最终应付的钱数。

示例 1

输入

4

10 20 10 20

25 10

输出

25

说明

四个菜一共 60 元，满减减掉了 25 元，再用一个 10 元的红包，因此需要付 25 元。

#include <iostream>
using namespace std;

int main() {
    int num;
    long long sum = 0;
    cin >> num;
    for (int i = 0; i < num; i++) {
        long long temp;
        cin >> temp;
        sum += temp;
    }
    long long l1, l2;
    cin >> l1 >> l2;
    sum = sum - l1 - l2;
    cout << sum << endl;
    return 0;
}

2.小美的合法单词

小美定义以下三种单词是合法的：

1. 所有字母都是小写。例如：good
2. 所有字母都是大写。例如：APP
3. 第一个字母大写，后面所有字母都是小写。例如：Alice

现在小美拿到了一个单词，她每次操作可以修改任意一个字符的大小写。小美想知道最少操作几次可以使得单词变成合法的？

输入描述

一个仅由大写字母和小写字母组成的字符串，长度不超过10^5。

输出描述

一个整数，代表操作的最小次数。

示例 1

输入

AbC

输出

1

说明

变成 ABC 或者 Abc 均可。只需要一次操作。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    string s;
    getline(cin, s);
    int small = 0, big = 0;
    int res = s.length();
    for (size_t i = 0; i < s.length(); ++i) {
        if(s[i] >= 'a' && s[i] <= 'z') small++;
        else if(s[i] >= 'A' && s[i] <= 'Z') big++;
    }
    int temp = s.length();
    if(s[0] >= 'A' && s[0] <= 'Z') temp = s.length() - 1 - small;
    res = min({small, big, temp}); // 使用min函数计算三个数中的最小值
    cout << res << endl;
    return 0;
}

3、翻倍元素

小美拿到了一个数组，她每次操作会将除了第x个元素的其余元素翻倍，一共操作了q次。请你帮小美计算操作结束后所有元素之和。

由于答案过大，请对10^9+7取模。

输入描述

第一行输入两个正整数n,q，代表数组的大小和操作次数。 第二行输入n个正整数ai，代表数组的元素。 第三行输入一个正整数q，代表操作的次数。 接下来的q行，每行输入一个正整数xi，代表第i次操作未被翻倍的元素。 1<=n,q<=10^5 1<=xi<=n 1<=ai<=10^9

输出描述

一个整数，代表操作结束后所有元素之和模10^9+7的值。

示例

输入

4 2 1 2 3 4 1 2

输出

34

说明

第一次操作后，数组变成[1,4,6,8] 第二次操作后，数组变成[2,4,12,16] 所有元素之和为 34。

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;

// 快速幂算法
long long fast_power(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

// 主函数，解决问题
long long solve(int n, int q, vector<int>& a, vector<int>& operations) {
    // 初始化跳过计数数组
    vector<int> skip_count(n, 0);
    
    // 计算每个元素被跳过的次数
    for (int x : operations) {
        skip_count[x - 1]++; 
    }
    
    // 计算最终的和
    long long final_sum = 0;
    for (int i = 0; i < n; i++) {
        // 计算元素ai的最终乘数
        long long element_power = fast_power(2, q - skip_count[i], MOD); //计算2的幂，就是翻倍的次数
        long long final_value = (static_cast<long long>(a[i]) * element_power) % MOD;
        
        // 累加到最终和
        final_sum = (final_sum + final_value) % MOD;
    }
    
    return final_sum;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> operations(q);
    for (int i = 0; i < q; i++) {
        cin >> operations[i];
    }
    
    cout << solve(n, q, a, operations) << endl;
    return 0;
}

4.小美的众数

小美拿到了一个数组。她希望你求出所有区间众数之和。你能帮帮她吗？

定义区间的众数为出现次数最多的那个数。如果有多个数出现次数最多，那么众数是其中最小的那个数。

输入描述

第一行输入一个正整数n，代表数组的大小。

第二行输入n个正整ai，代表数组的元素。

1<=n<=200000

1<=ai<=2

输出描述

一个正整数，代表所有区间的众数之和。

示例 1

输入

3

2 1 2

输出

9

说明

[2],[2,1,2],[2]的众数是 2。[2,1],[1],[1,2]的众数是 1。因此答案是 9。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    const int MOD = 1000000007;
    long long result = 0;

    // 用于存储1和2的数量
    vector<long long> count_1(n + 1, 0), count_2(n + 1, 0);

    // 初始化前缀和数组
    for (int i = 0; i < n; i++) {
        count_1[i + 1] = count_1[i] + (arr[i] == 1);
        count_2[i + 1] = count_2[i] + (arr[i] == 2);
    }

    // 遍历所有可能的子区间
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int c1 = count_1[j + 1] - count_1[i];  // 从i到j的1的数量
            int c2 = count_2[j + 1] - count_2[i];  // 从i到j的2的数量
            if (c1 > c2) {
                result += 1;
            } else if (c1 < c2) {
                result += 2;
            } else { // c1 == c2
                result += min(arr[i], arr[j]);
            }
            result %= MOD;
        }
    }

    cout << result << endl;
    return 0;
}