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;
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/99972856