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

#字节笔试#
四道编程 C++解法
第一题 木板可收集雨水的最大量
int main() {
int n;
cin >> n;
priority_queue pq;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
pq.push(x);
}
pq.pop();
cout << static_cast(n - 1) * pq.top();
}

第二题 数组按顺序插入双端队列可否保证有序(非严格递增)
int main() {
int T, n;
cin >> T;
for (int i = 0; i < T; ++i) {
cin >> n;
vector nums(n - 1);
int l, r;
cin >> l; r = l;
for (auto& 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 ? "YES\n" : "NO\n");
}
}

第三题 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(a, b), Nbc = lcm(b, c), Nac = lcm(a, c);
ll N = lcm(Nab, c);
int res = n / Nab + n / Nbc + n / Nac - n / N * 2;
cout << res << '\n';
}
}

第四题 最大值不重复的子数组个数(没做出来,通过10%)
int main() {
int n;
cin >> n;
vector nums(n);
for (auto& x : nums)cin >> x;
using pii = pair;
stack stk;
queue q;
for (int i = 0; i < n; ++i) {
int x = nums[i];
while (!stk.empty() && stk.top().first < x) {
stk.pop();
}
if (!stk.empty() && 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 && nums[i] < x)--i;
while (j < n && nums[j] < x)++j;
res -= (long long)(l - i) * (j - r);
}
cout << res;
}
全部评论
第三题过了5%,第四题过了15.79%,寄
点赞 回复 分享
发布于 09-29 21:20 山东
第三题暴力25,第四题暴力15
点赞 回复 分享
发布于 09-29 21:23 黑龙江
第二题基本上写的一模一样,一跑就是0%,这么简单跑不出来,我吐了
点赞 回复 分享
发布于 09-29 21:29 辽宁
第一题是要用int64才能过吗?
点赞 回复 分享
发布于 09-29 21:32 黑龙江

相关推荐

头像
11-07 14:59
东北大学 Java
点赞 评论 收藏
分享
1 6 评论
分享
牛客网
牛客企业服务