美团8月20日全AK代码

1. 两个字符串循环插入

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    string A, B;
    cin >> A >> B;
    string res = "";
    for (int i = 0; i < n; i++)
    {
        res = res + A[i] + B[i];
    }
    cout << res << endl;
    return 0;
}

2. 已知三个点(x1,y1), (x2, y2), (x3, y3)的坐标，以及三个点到目标(a,b)点的曼哈顿距离d1,d2,d3 求，(a,b)字典序的最小值

思路：正常可以通过2次循环模拟，但是会超时，可以将abs(y-b)的值存储起来，然后在遍历abs(x-a) 查看 abs(y-b)是否对应同一个b即可

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int x1, y1, x2, y2, x3, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    int d1, d2, d3;
    cin >> d1 >> d2 >> d3;
    int a, b;
    unordered_map<int, unordered_map<int, bool>> ymap1;
    unordered_map<int, unordered_map<int, bool>> ymap2;
    unordered_map<int, unordered_map<int, bool>> ymap3;
    for (int i = 1; i <= n; i++)
    {
        ymap1[abs(y1 - i)][i] = true;
        ymap2[abs(y2 - i)][i] = true;
        ymap3[abs(y3 - i)][i] = true;
    }
    for (int i = 1; i <= n; i++)
    {

        if (ymap1.count(d1 - abs(x1 - i)) > 0 &&
            ymap2.count(d2 - abs(x2 - i)) > 0 && ymap3.count(d3 - abs(x3 - i)) > 0)
        {
            int j = -1;
            for (auto &s : ymap1[d1 - abs(x1 - i)])
            {
                if (ymap2[d2 - abs(x2 - i)][s.first] &&
                    ymap3[d3 - abs(x3 - i)][s.first])
                {
                    j = s.first;
                    break;
                }
            }
            if (j == -1)
                continue;
            a = i;
            b = j;
            cout << a << " " << b << endl;
            return 0;
        }
    }
    return 0;
}

3. 已值n个题目，每个题目得分为有p / 100的概率得到val的分数，1 - p/100得分为0，然后可以选择m个进行复习，把概率提升到100%，问最多可以获得多少分

思路：每个题可以获得如果提升到100%然后提升的分数(1- p/100) * val，然后对该提高的分数排序即可，对前m个进行分数提高剩下的不变，则是最高分数（注意有精度要求，把所有的变量定位double，否则通过不了）

#include <bits/stdc++.h>

using namespace std;

struct node
{
    double p;
    double val;
    double add;
};
bool cmp(struct node &a, struct node &b)
{
    return a.add > b.add;
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<node> vals(n);
    for (int i = 0; i < n; i++)
    {
        double p;
        cin >> p;
        vals[i].p = p / 100.0;
    }
    for (int i = 0; i < n; i++)
    {
        cin >> vals[i].val;
        vals[i].add = (1.0 - vals[i].p) * vals[i].val;
    }
    sort(vals.begin(), vals.end(), cmp);
    double res = 0;
    for (int i = 0; i < n; i++)
    {
        if (i < m)
            res += vals[i].val;
        else
            res += vals[i].p * vals[i].val;
    }
    printf("%.2f", res);
    return 0;
}

4. 有两个队列A, B，可以对A或者B中的一个值进行变换，一种是将值给消除，代价为|a|,一种是将值变成另外一个数，代价为|b-a|，请问将A,B变成相同数列的最小代价

思路： leetcode编辑距离的变形

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> A(n);
    vector<int> B(m);
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
        dp[i + 1][0] += abs(A[i]) + dp[i][0];
    }
    for (int i = 0; i < m; i++)
    {
        cin >> B[i];
        dp[0][i + 1] += abs(B[i]) + dp[0][i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            dp[i][j] = min(dp[i - 1][j - 1] + abs(B[j - 1] - A[i - 1]),
                           dp[i - 1][j - 1] + abs(B[j - 1]) + abs(A[i - 1]));
            dp[i][j] = min(dp[i][j], min(dp[i][j - 1] + abs(B[j - 1]), dp[i - 1][j] + abs(A[i - 1])));
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

5. 有B，包含了一系列需要处理的材料b1,b2,b3，然后需要用A中的材料进行处理，满足 aij > b1，a中的元素可以无限使用，请问最少使用的A的材料是多少，不满足返回-1

思路：遍历B，排序A，然后二分查找A，时间复杂度 min(n,m) log2m

#include <bits/stdc++.h>

using namespace std;

int binarySearch(vector<int> &nums, int target)
{
    int l = 0, r = nums.size() - 1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (nums[mid] == target)
        {
            return mid;
        }
        else if (nums[mid] < target)
        {
            l = mid + 1;
        }
        else
        {
            r = mid;
        }
    }
    return l;
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> B(n);
    vector<int> A(m);
    for (int i = 0; i < n; i++)
        cin >> B[i];
    for (int i = 0; i < m; i++)
        cin >> A[i];
    sort(A.begin(), A.end());
    long long res = 0;
    for (int i = 0; i < n; i++)
    {
        if (B[i] > A[m - 1])
        {
            cout << -1 << endl;
            return 0;
        }
        int idx = binarySearch(A, B[i]);
        res += A[idx];
    }
    cout << res << endl;
    return 0;
}

#美团笔试#