题目描述
滑动窗口
STL真的可以让算法很简单哦!!!
另外加了一道蓝桥的省赛题目,题目难度是有的
样例
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main()
{
int n,k; cin >> n >> k;
for(int i = 1 ; i <= n ; i ++) cin >> a[i];
deque<int> q;
for(int i = 1 ; i <= n ; i++)
{
while(q.size() && q.back() > a[i]) q.pop_back();
q.push_back(a[i]);
if(i - k >= 1 && q.front() == a[i-k])
q.pop_front();
if(i >= k) cout << q.front() << " ";
}
q.clear();
cout << endl;
for(int i = 1 ; i <= n ; i++)
{
while(q.size() && q.back() < a[i]) q.pop_back();
q.push_back(a[i]);
if(i-k >= 1 && a[i-k] == q.front()) q.pop_front();
if(i >= k) cout << q.front() << " ";
}
return 0;
}
蓝桥题目链接 >>> https://www.lanqiao.cn/problems/2109/learning/?page=1&first_category_id=1&second_category_id=3&status=3
这道题也用了滑动窗口的思想.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <deque>
#define int long long
using namespace std;
const int N = 510;
int n,m,k;
int a[N][N];
signed main()
{
cin >> n >> m >> k;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= m ; j++)
cin >> a[i][j],a[i][j] +=a[i-1][j];//列向量
int ans = 0;
for(int i = 1 ; i <= n ; i++)
for(int ii = i ; ii <= n ; ii++)
{
int l = 1,r = 1;
int sum = 0;
for( ; r <= m ; r++)
{
sum += a[ii][r] - a[i-1][r];
while(sum > k)
{
sum -= a[ii][l] - a[i-1][l];
l++;
}
ans+=r-l+1;
}
}
cout << ans << endl;
return 0;
}