百度笔试-算法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;
} 