PAT-A-1044 Shopping in Mars (25 分)滑動視窗、隊列的使用 C++題解

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