2022.8.13美团笔试

#include <iostream>

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
struct Linklist {
    int val;
    Linklist* pre, * next;
};

int findNext(vector<int>& nums, int l, int r, int target) {
    if (l == nums.size()) return r + 1;
    if (nums[l] >= target) return l;
    if (nums[r] < target) return r + 1;
    while (r - l > 1) {
        int mid = (r - l) / 2 + l;
        if (nums[mid] >= target) {
            r = mid;
        }
        else {
            l = mid;
        }
    }
    return r;

}
int main()
{

    int n, t;
    cin >> n >> t;
    vector<int> limit;
    for (int i = 0; i < n; i++) {
        int cur;
        cin >> cur;
        limit.push_back(cur);
    }
    sort(limit.begin(), limit.end());
    int ans = 0;
    int cur_limit = 0, last_pos = 0;
    while (cur_limit < limit[limit.size() - 1]) {
        //贪心找最小能完成的
        cur_limit += t;
        int index = findNext(limit, last_pos, limit.size() - 1, cur_limit);
        if (index == limit.size()) {
            break;
        }
        last_pos = index + 1;
        //cout << "last_pos " << last_pos <<endl;
        ans++;
    }
    cout << limit.size() - ans;

}

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    /* int n, t;
     cin >> n >> t;
     vector<int> limit;
     for (int i = 0; i < n; i++) {
         int cur;
         cin >> cur;
         limit.push_back(cur);
     }
     sort(limit.begin(), limit.end());
     int ans = 0;
     for (int i = 0; i < limit.size(); i++) {

     }*/
    int n, m, k;
    cin >> n >> m >> k;
    vector<char> input;
    for (int i = 0; i < k; i++) {
        char a;
        cin >> a;
        input.push_back(a);
    }
    vector<vector<int>> vis(n, vector<int>(m));
    int cur_r = 0, cur_l = 0, cur_size = 1;
    vis[0][0] = 1;

    for (int i = 0; i < k; i++) {
        switch (input[i])
        {
        case 'A':
            cur_l -= 1;
            if (vis[cur_r][cur_l] == 0) {
                cur_size++;
                vis[cur_r][cur_l] = 1;
            }
            break;
        case 'S':
            cur_r += 1;
            if (vis[cur_r][cur_l] == 0) {
                cur_size++;
                vis[cur_r][cur_l] = 1;
            }
            break;
        case 'D':
            cur_l += 1;
            if (vis[cur_r][cur_l] == 0) {
                cur_size++;
                vis[cur_r][cur_l] = 1;
            }
            break;
        case 'W':
            cur_r -= 1;
            if (vis[cur_r][cur_l] == 0) {
                cur_size++;
                vis[cur_r][cur_l] = 1;
            }
            break;
        default:
            break;
        }
        if (cur_size == n * m) {
            cout << "Yes" << endl;
            cout << i + 1 << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    cout << n * m - cur_size << endl;

}

#include <iostream>

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
struct Linklist {
    int val;
    Linklist* pre, * next;
};
int main()
{
    Linklist* head = new Linklist();
    Linklist* cur = head;
    Linklist* head_opt = new Linklist();
    Linklist* cur_opt = head_opt;
    int n;
    cin >> n;
    vector<int> input;
    unordered_map<Linklist*, Linklist*> map;
    map[head] = head_opt;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        input.push_back(a);
        if (i == n - 1) break;
        Linklist* temp = new Linklist();
        cur->next = temp;
        temp->pre = cur;
        cur = temp;

        Linklist* temp_opt = new Linklist();
        cur_opt->next = temp_opt;
        temp_opt->pre = cur_opt;
        cur_opt = temp_opt;
        map[cur] = cur_opt;
    }
    head->pre = cur;
    cur->next = head;
    head_opt->pre = cur_opt;
    cur_opt->next = head_opt;

    Linklist* t = head;
    for (int i = 0; i < n; i++) {
        if (i == n - 1) {
            map[t]->val = input[i];
            break;
        }
        //移动
        t = t->next->next;
        t->val = input[i];
        map[t]->val = input[i];

        //delete
        t->pre->next = t->next;
        t->next->pre = t->pre;
        t = t->next;
    }
    for (int i = 0; i < n; i++) {
        cout << head_opt->val << " ";
        head_opt = head_opt->next;
    }
    /* int n, t;
     cin >> n >> t;
     vector<int> limit;
     for (int i = 0; i < n; i++) {
         int cur;
         cin >> cur;
         limit.push_back(cur);
     }
     sort(limit.begin(), limit.end());
     int ans = 0;
     for (int i = 0; i < limit.size(); i++) {

     }*/

}

#include <iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> input;
    for (int i = 0; i < n; i++) {
        int s;
        cin >> s;
        input.push_back(s);
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (input[i] == 3 * input[j] - input[k]) {
                    ans++;
                }
            }
        }
    }
    cout << ans;
}

#include<vector>
#include<algorithm>
#include <iostream>
using namespace std;
int dp(int root, vector<int>& input) {
    if (root >= input.size()) return 0;
    int max_money = max(dp(root * 2, input), dp(root * 2 + 1, input));
    return input[root] + max_money;
}
int main()
{
    int n;
    cin >> n;
    vector<int> input(n + 1);
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        input[i] = a;
    }
    cout << dp(1, input);

}