字节抖音客户端笔试 09-29

#字节笔试#
四道编程 C++解法
第一题 木板可收集雨水的最大量
int main() {
int n;
cin >> n;
priority_queue<int> pq;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
pq.push(x);
}
pq.pop();
cout << static_cast<long long>(n - 1) * pq.top();
}
第二题 数组按顺序插入双端队列可否保证有序(非严格递增)
int main() {
int T, n;
cin >> T;
for (int i = 0; i < T; ++i) {
cin >> n;
vector<int> nums(n - 1);
int l, r;
cin >> l; r = l;
for (auto&amp; x : nums)cin >> x;
bool flag = true;
for (auto x : nums) {
if (x <= l)l = x;
else if (x >= r)r = x;
else {
flag = false;
break;
}
}
cout << (flag ? &quot;YES\n&quot; : &quot;NO\n&quot;);
}
}
第三题 n天内做超过两件事的天数
int main() {
using ll = long long;
int T, n, a, b, c;
cin >> T;
for (int k = 0; k < T; ++k) {
cin >> n >> a >> b >> c;
ll Nab = lcm<ll, ll>(a, b), Nbc = lcm<ll, ll>(b, c), Nac = lcm<ll, ll>(a, c);
ll N = lcm<ll, ll>(Nab, c);
int res = n / Nab + n / Nbc + n / Nac - n / N * 2;
cout << res << '\n';
}
}
第四题 最大值不重复的子数组个数(没做出来，通过10%)
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (auto&amp; x : nums)cin >> x;
using pii = pair<int, int>;
stack<pii> stk;
queue<pii> q;
for (int i = 0; i < n; ++i) {
int x = nums[i];
while (!stk.empty() &amp;&amp; stk.top().first < x) {
stk.pop();
}
if (!stk.empty() &amp;&amp; stk.top().first == x) {
q.emplace(stk.top().second, i);
stk.pop();
}
stk.emplace(x, i);
}
long long res = (long long)n * (1 + n) / 2;
while (!q.empty()) {
auto [l, r] = q.front(); q.pop();
int x = nums[l];
int i = l - 1, j = r + 1;
while (i >= 0 &amp;&amp; nums[i] < x)--i;
while (j < n &amp;&amp; nums[j] < x)++j;
res -= (long long)(l - i) * (j - r);
}
cout << res;
}