1044 Shopping in Mars (25 分)
题目传送门:1044 Shopping in Mars (25 分)
一、题目大意
求长度为n的数组中,和为m的所有子数组,输出所有子数组的左右下标。如果没有和为m的子数组,则输出最小的和超过m的子数组。
二、解题思路
通过队列保存滑动窗口,并且通过一个变量sum同步保存当前滑动窗口里子数组的和。
循环判断当窗口里的子数组和大于等于m时,则将区间信息和子数组和保留到结果集中,然sum减去队首元素的值,并且队列第一个元素出队。
然后往队列里顺序压值。具体操作如下代码。
此时结果集中存放的都是子数组和大于等于m的,对结果集按照子数组和排个序,输出最小的子数组和的元素即可。
三、AC代码
#include<bits/stdc++.h>
using namespace std;
template<typename T = int>
T read(){
T x;
cin >> x;
return x;
}
struct Node
{
int left, right, sum;
bool operator<(const Node& that)const{
if(sum != that.sum)
return sum < that.sum;
return left < that.left;
}
};
int main(){
int n = read(), m = read();
vector<int>v;
for(int i = 0; i < n; i++){
v.push_back(read());
}
deque<pair<int, int>>D;
vector<Node>res;
int sum = 0;
for(int i = 0; i < n; i++){
while(sum >= m){
res.push_back({D.front().first+1, i, sum});
sum -= D.front().second;
D.pop_front();
}
D.push_back({i, v[i]});
sum += v[i];
}
while(sum >= m){
res.push_back({D.front().first+1, n, sum});
sum -= D.front().second;
D.pop_front();
}
sort(res.begin(), res.end());
for(int i = 0; i < res.size(); i++){
if(res[i].sum > res[0].sum)break;
cout << res[i].left << '-' << res[i].right << endl;
}
}