8.20 美团笔试 AK题解

第一题很简单，就不描述了。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {
    //freopen("test.txt", "r", stdin);
    ios::sync_with_stdio(false);
    int n;
    string a, b, ans;
    cin >> n >> a >> b;
    for (int i = 0; i < n; ++i) {
        ans.push_back(a[i]);
        ans.push_back(b[i]);
    }
    cout << ans << endl;
    // 第一次没有输出回车，居然0%，醉了
    return 0;
}

第二题大意是，给三个点，给三个曼哈顿距离，求出一个点到这个三个点的曼哈顿距离满足题目给的要求，有多个就输出字典序较小的那个。
输入如下

3 //格子的大小，点的坐标要满足[1, n]
2 1 //第一个点
2 2 //第二个点
2 3 //第三个点
2 1 2 //分别对应的三个距离

我用的纯暴力，没啥好说的

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
set<pair<int, int>> res, ans;
int dir[][2] = {{1,  1},
                {1,  -1},
                {-1, 1},
                {-1, -1}};

set<pair<int, int>> find_dot(int x, int y, int d, int n) {
    set<pair<int, int>> tmp;
    for (int i = d; i >= 0; --i) {
        for (auto & k : dir) {
            int new_x = x + i * k[0], new_y = y + (d - i) * k[1];
            if (new_x >= 1 && new_x <= n && new_y >= 1 && new_y <= n) {
                tmp.insert(make_pair(new_x, new_y));
            }
        }


    }
    return tmp;
}

int main() {
    //freopen("test.txt", "r", stdin);
    ios::sync_with_stdio(false);
    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;
    set<pair<int, int>> dot1 = find_dot(x1, y1, d1, n);
    set<pair<int, int>> dot2 = find_dot(x2, y2, d2, n);
    set<pair<int, int>> dot3 = find_dot(x3, y3, d3, n);
    set_intersection(dot1.begin(), dot1.end(), dot2.begin(), dot2.end(), inserter(res, res.end()));
    set_intersection(res.begin(), res.end(), dot3.begin(), dot3.end(), inserter(ans, ans.end()));
    cout << ans.begin()->first << ' ' << ans.begin()->second;
    return 0;
}

第三题是n道题目，m次作弊机会，作弊就能拿到100%的分数，否则拿到输入给的百分比的分数

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

struct node {
    int a, b, c;

    node(int a, int b, int c) : a(a), b(b), c(c) {}
};

int main() {
//    freopen("test.txt", "r", stdin);
//    ios::sync_with_stdio(false);
    int n, m;
    double ans = 0.0;
    cin >> n >> m;
    vector<int> p(n), scores(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> scores[i];
    }
    vector<node> record;
    for (int i = 0; i < n; ++i) {
        record.push_back(node(p[i], scores[i], (100 - p[i]) * scores[i]));
    }
    sort(record.begin(), record.end(), [](node &x, node &y) {
        return x.c > y.c;
    });
    for (int i = 0; i < m; ++i) {
        ans += record[i].b;
    }
    for (int i = m; i < n; ++i) {
        ans += record[i].a * record[i].b / 100.0;
    }
    printf("%.2f", ans);
    return 0;
}

第四题，让两个数列变得一样。可以消去一个数a，代价是abs(a)，或者这个数a改成b，代价是abs(a-b)。最小的代价是多少（类似编辑距离）

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

int main() {
    freopen("test.txt", "r", stdin);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i < n + 1; ++i) {
        dp[i][0] = dp[i - 1][0] + abs(a[i - 1]);
    }
    for (int i = 1; i < m + 1; ++i) {
        dp[0][i] = dp[0][i - 1] + abs(b[i - 1]);
    }
    for (int i = 1; i < n + 1; ++i) {
        for (int j = 1; j < m + 1; ++j) {
            if (a[i - 1] == b[i - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min(abs(a[i-1] - b[j-1]) + dp[i - 1][j - 1], min(dp[i - 1][j] + abs(a[i - 1]), dp[i][j - 1] + abs(b[j - 1])));
        }
    }
    cout << dp[n][m];
    return 0;
}

第五题，两行数字，n和m个。从m个数字选出能cover住n个数字的序列，m序列每个不限量，最小代价是多少。不能满足就是-1

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

int main() {
    //freopen("test.txt", "r", stdin);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> b(n);
    set<int> a;
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    for (int i = 0; i < m; ++i) {
        int tmp;
        cin >> tmp;
        a.insert(tmp);
    }
    LL ans = 0;
    //sort(a.begin(), a.end());
    for (int i = 0; i < n; ++i) {
        int target = b[i];
        auto iter = a.lower_bound(target);
        if (iter == a.end()) {
            ans = -1;
            break;
        }
        ans += *iter;
    }
    cout << ans;
    return 0;
}