饿了么笔试 20230825

三道编程：AC、AC、70%

第一题。给定一个包含n个字符串的集合，给了一个数组，包含k个字符串，全都在集合内出现过。

按次序输出前m项，优先输出出现出现次数多的，相同时优先输出字典序更小的。

解：用map做string到 [1,n] 的映射，然后根据要求排序数对。AC

#include <bits/stdc++.h>
#define pii pair<string, int>
using namespace std;

map<string, int> mp;
vector<pii> vs;
int n, m, k;

bool cmp(pii x, pii y)
{
    return x.second == y.second ? x.first < y.first : x.second > y.second;
}

int main()
{
    cin >> n >> m;
    vs.resize(n);
    for (int i = 0; i < n; ++i)
    {
        string temp;
        cin >> temp;
        vs[i].first = temp;
    }
    cin >> k;
    for (int i = 0; i < k; ++i)
    {
        string temp;
        cin >> temp;
        if (mp.count(temp) != 0)
            mp[temp]++;
        else
            mp.insert({temp, 1});
    }
    for (int i = 0; i < n; ++i)
        if (mp.count(vs[i].first))
            vs[i].second = mp[vs[i].first];
    sort(vs.begin(), vs.end(), cmp);
    for (int i = 0; i < m; ++i)
        cout << vs[i].first << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

第二题，n<1000个小区名，有m条道路，道路有长度。有k<1000个订单，订单有商家所在小区和顾客所在小区。问从家所在的小区出发，完成两个订单并回家的最短路程。

floyd + 暴力枚举。先用floyd算出任意两小区之间的最短距离，再暴力枚举接哪两个订单，以及到达的顺序（A商家-A顾客-B商家-B顾客，A商家-B商家-A顾客-B顾客，A商家-B商家-B顾客-A顾客）。AC

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
typedef long long ll;
const int N = 205;
const int M = 1005;
const int INF = 1e9 + 7;

map<string, int> mp;
vector<pii> g[N];
int n, m, cnt;
int dis[N][N];
int q;
int fm[M], to[M];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            dis[i][j] = i == j ? 0 : INF;

    for (int i = 0; i < m; ++i)
    {
        string s1, s2;
        int id1, id2, w;
        cin >> s1 >> s2 >> w;
        if (mp.count(s1))
            id1 = mp[s1];
        else
        {
            mp.insert({s1, ++cnt});
            id1 = cnt;
        }
        if (mp.count(s2))
            id2 = mp[s2];
        else
        {
            mp.insert({s2, ++cnt});
            id2 = cnt;
        }
        dis[id1][id2] = min(dis[id1][id2], w);
        dis[id2][id1] = min(dis[id2][id1], w);
    }

    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

    cin >> q;
    for (int i = 1; i <= q; ++i)
    {
        string s1, s2;
        cin >> s1 >> s2;
        fm[i] = mp[s1];
        to[i] = mp[s2];
    }

    string hm;
    int home;
    cin >> hm;
    home = mp[hm];

    ll ans = INF;
    for (int i = 1; i <= q; ++i)
    {
        for (int j = 1; j <= q; ++j)
        {
            if (i == j)
                continue;

            ll tot = 0;
            tot += dis[home][fm[i]];
            tot += dis[fm[i]][to[i]];
            tot += dis[to[i]][fm[j]];
            tot += dis[fm[j]][to[j]];
            tot += dis[to[j]][home];
            ans = min(ans, tot);

            tot = 0;
            tot += dis[home][fm[i]];
            tot += dis[fm[i]][fm[j]];
            tot += dis[fm[j]][to[i]];
            tot += dis[to[i]][to[j]];
            tot += dis[to[j]][home];
            ans = min(ans, tot);

            tot = 0;
            tot += dis[home][fm[i]];
            tot += dis[fm[i]][fm[j]];
            tot += dis[fm[j]][to[j]];
            tot += dis[to[j]][to[i]];
            tot += dis[to[i]][home];
            ans = min(ans, tot);
        }
    }
    cout << ans << endl;
    return 0;
}

第三题，给定一个循环数组，长度小于1e5，当相邻项相同时，自动删除其中一个。每次你可以执行手动删除，删除其中一个元素。问你最多可以手动删除几次。保证开始时数组没有相邻相同的元素。

例：1212，删除2后两个1相邻，会自动删除一个1，所以是3。12123，答案是5。

过了70%： 从左到右遍历，如果第i与i+2相同，第i+1与i+3相同时，i++，且ans--。最后ans+=n。应该也是一个瞎搞的思路了，没想到能过70%。12125输进去都是错的。

想到过但被自己否了结果看牛友说是正解的办法：如果有三种以上的指，输出n，否则就是12121212这种，输出n/2+1。