3.25美团前端笔试

选择题有点难。。。

算法100 100

希望能过这个笔试吧

1.直接栈模拟

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

typedef pair<int, int> pii;
typedef long long ll;
#define rep(i, start, end) for (int i = start; i <= end; i++)
#define lop(i, start, end) for (int i = start; i >= end; i--)
int main() {
    int T;
    cin >> T;
    rep(i, 1, T) {
        int n;
        cin >> n;
        vector<int> x, y, st;
        rep(j, 1, n) {
            int tmp;
            cin >> tmp;
            x.push_back(tmp);
        }
        rep(j, 1, n) {
            int tmp;
            cin >> tmp;
            y.push_back(tmp);
        }

        int iy = 0;
        rep(k, 0, n - 1) { // 考虑x的每一辆车
            st.push_back(x[k]);
            while (!st.empty() && st.back() == y[iy]) { // 符合就快出去
                st.pop_back(), iy++;
            }
        }
        if (iy == n) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

2.直接贪心查找就行，没搞懂

可能有用的优化手段：注意到查询q非常大，有可能直接超了，先统计全部的和

排序+二分，从尽可能大的重量开始装

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

typedef pair<int, int> pii;
typedef long long ll;
#define rep(i, start, end) for (int i = start; i <= end; i++)
#define lop(i, start, end) for (int i = start; i >= end; i--)
int main() {
    int n, m, all = 0;
    vector<int> v;
    cin >> n >> m;
    rep(i, 1, n) {
        int tmp;
        cin >> tmp;
        v.push_back(tmp * tmp);
        all += tmp * tmp;
    }
    sort(v.begin(), v.end());
    rep(i, 1, m) { // 对于每一次询问
        ll q, res = 0;
        cin >> q;
        if (q >= all) {
            cout << n << endl;
            continue;
        }
        int idx = upper_bound(v.begin(), v.end(), q) - v.begin();
        if (idx == n) {
            idx--;
        }
        for (; idx >= 0 && q > 0; idx--) {
            if (q - v[idx] >= 0) {
                res++;
                q -= v[idx];
            }
        }
        cout << res << endl;
    }
    return 0;
}