链接

题意：给一个N * M的矩阵，求出有多少个子矩阵小于k。

题解：一维前缀和+双指针算法。s[i][j]表示第j列前i个元素的和。这种类型的题确定一条边界，然后再对另外一条边界伸缩进行求解。本题先确定上下边界，然后让右边界右移，如果范围内的总和大于k，左边界右移。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <math.h>
#include <string>
#define PI 3.14159
using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
const int MAX_INT = 0x3f3f3f3f;
const int N = 5e2 + 15;
const int mod = 1e9 + 7;
int s[N][N]; //列的前缀和

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> s[i][j];
            s[i][j] += s[i - 1][j];//列的一维前缀和
        }
    }

    LL res = 0;
    for (int i = 1; i <= n; i++)//确定上边界
    {
        for (int j = i; j <= n; j++)//确定下边界
        {

            for (int l = 1, r = 1, sum = 0; r <= m; r++)//控制右边界
            {
                sum += s[j][r] - s[i - 1][r];
                while (sum > k)//控制左边界
                {
                    sum -= (s[j][l] - s[i - 1][l]);
                    l++;
                }
                res += r - l + 1;//统计
            }
        }
    }
    cout << res << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    while (T--)
    {
        solve();
    }
}