2023-09-03 12:06 东南大学 C++
关注
饿了么9.2笔试第三题
题目：正整数数组a和整数k，删除一个元素的情况下，找总和不小于k的子数组的最短长度。
当时没好的思路，只滑动窗口暴力骗了些分数。后面补了一下觉得可以边滑窗边维护滑窗最小值，相减满足就可以尝试更新答案。所以用滑动窗口+单调队列实现的。不知道有没有问题，没法检验了。
# include <bits/stdc++.h>
using namespace std;
int main() {
using ll = long long;
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &i : a) cin >> i;
deque<int> win_min;
int l = 0, r = 0, ans = INT_MAX;
ll cur = 0;
while(r < n) {
while(!win_min.empty() && a[win_min.back()] > a[r])
win_min.pop_back();
win_min.push_back(r);
cur += a[r];
while(cur - a[win_min.front()] >= k) {
ans = min(ans, r-l);
if (win_min.front() == a[l])
win_min.pop_front();
cur -= a[l++];
}
r++;
}
cout << ans << endl;
return 0;
}
当时没好的思路，只滑动窗口暴力骗了些分数。后面补了一下觉得可以边滑窗边维护滑窗最小值，相减满足就可以尝试更新答案。所以用滑动窗口+单调队列实现的。不知道有没有问题，没法检验了。
# include <bits/stdc++.h>
using namespace std;
int main() {
using ll = long long;
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &i : a) cin >> i;
deque<int> win_min;
int l = 0, r = 0, ans = INT_MAX;
ll cur = 0;
while(r < n) {
while(!win_min.empty() && a[win_min.back()] > a[r])
win_min.pop_back();
win_min.push_back(r);
cur += a[r];
while(cur - a[win_min.front()] >= k) {
ans = min(ans, r-l);
if (win_min.front() == a[l])
win_min.pop_front();
cur -= a[l++];
}
r++;
}
cout << ans << endl;
return 0;
}
全部评论
相关推荐
查看12道真题和解析 02-09 14:23
西安建筑科技大学 数据分析师 点赞 评论 收藏
分享
点赞 评论 收藏
分享