百度笔试-算法A卷

1. 通关 AC

题目大概意思：两个数组和一个t，选择和不超过t的最大个数

思路：构建两者前缀和，遍历小的一个，对于另一个数组二分查找位置，记录maxn

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;
int main() {
    int n, m, t;
    cin >> n >> m >> t;
    vector<ll> g1(n+1), g2(m+1);
    for(int i = 1; i <= n; i++) {
       cin >> g1[i];
       g1[i] += g1[i - 1];
    }
    for(int j = 1; j <= m; j++) {
      cin >> g2[j];
      g2[j] += g2[j - 1];
    }
    g1.push_back(LONG_MAX);
    g2.push_back(LONG_MAX);
    ll max_cnt = 0;
    for(int i = 0; i <= g1.size() && g1[i] <= t; i++) {
        int cnt;
        int idx = lower_bound(g2.begin(), g2.end(), t - g1[i]) - g2.begin();
        if(idx < g2.size() && g2[idx] == t - g1[i]) {
           cnt = i + idx;
        } else {
           cnt = i + idx - 1;
        } max_cnt = max(max_cnt, cnt);
    }
    cout << max_cnt;
    return 0;
}

2. AC

// 给数组排m次序

// 输入一 n 个数组成的数组，进行了m次操作

// 每次操作由 a b 两个数定义

// a==1 表示把数组的前 b 个数从小到大排序

// a==2 表示把数组的前 b 个数从大到小排序。

// 输出m次操作后的数组

// 1≤n,m≤2x1e5

// n个整数属于 [-1e9,1e9]范围

// 1≤a≤2，1≤b≤n

// 输出描述

// 输入

// 4 2 （n、m）

// 1 2 4 3 （n个数）

// 2 3 （第一次操作，得到 4 2 1 3）

// 1 2 （第二次操作）

// 输出

// 2 4 1 3

思路：单调栈，发现如果对于操作 i j，操作j位于操作i之后，并且ki < kj，那么kj可以覆盖ki，因此无需操作ki

#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
struct node {
    int t, k;
    node(int _t, int _k):t(_t), k(_k) {}
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) cin >> nums[i];
    deque<node> dq;
    int t, k;
    for(int i = 0; i < m; i++) {
        cin >> t >> k;
        while(!dq.empty() && dq.back().k < k) {
            dq.pop_back();
        }
        dq.emplace_back(t, k);
    }
    for(auto& it: dq) {
        if(it.t == 1) {
            sort(nums.begin(), nums.begin() + it.k);
        } else {
            sort(nums.begin(), nums.begin() + it.k, greater<int>());
        }
    }
    for_each(nums.begin(), nums.end(), [&](int &num){cout << num << " ";});
    return 0;
}

#百度笔试##百度笔试机器学习##百度算法笔试##百度23秋招笔试编程题有点儿简单啊#