2019牛客多校第三场F Planting Trees（单调队列）题解

た入场券 2021-11-05 02:06 281阅读 0赞

# 题意： #

求最大矩阵面积，要求矩阵内数字满足\\(max - min < m\\)

# 思路： #

枚举上下长度，在枚举的时候可以求出每一列的最大最小值\\(cmax，cmin\\)，这样问题就变成了求一行数，要你得到\\(max - min < m\\)的最长长度。用单调队列\\(O(n)\\)求解。总复杂度\\(O(n^3)\\)。

# 代码： #

#include<map> #include<set> #include<cmath> #include<cstdio> #include<stack> #include<ctime> #include<vector> #include<queue> #include<cstring> #include<string> #include<sstream> #include<iostream> #include<algorithm> #define ll long long using namespace std; const int maxn = 500 + 5; const int INF = 0x3f3f3f3f; const ll MOD = 1e9 + 7; using namespace std; int n, m; int a[maxn][maxn]; int cmax[maxn], cmin[maxn]; //递减 递增 int maxq[maxn], minq[maxn]; int getans(){ int maxhead = 0, maxtail = 0, minhead = 0, mintail = 0; int l = 1; int len = 0; for(int i = 1; i <= n; i++){ while(maxhead < maxtail && cmax[i] > cmax[maxq[maxtail - 1]]) maxtail--; maxq[maxtail++] = i; while(minhead < mintail && cmin[i] < cmin[minq[mintail - 1]]) mintail--; minq[mintail++] = i; while(minhead < mintail && maxhead < maxtail && cmax[maxq[maxhead]] - cmin[minq[minhead]] > m){ l = min(maxq[maxhead], minq[minhead]) + 1; //跳到l + 1 while(minhead < mintail && minq[minhead] < l) minhead++; while(maxhead < maxtail && maxq[maxhead] < l) maxhead++; } len = max(len, i - l + 1); } return len; } int main(){ int T; scanf("%d", &T); while(T--){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ scanf("%d", &a[i][j]); } } int ans = 0; for(int i = 1; i <= n; i++){ //从i for(int j = 1; j <= n; j++){ cmax[j] = -1; cmin[j] = INF; } for(int j = i; j <= n; j++){ //到j for(int k = 1; k <= n; k++){ cmax[k] = max(cmax[k], a[j][k]); cmin[k] = min(cmin[k], a[j][k]); } ans = max(ans, (j - i + 1) * getans()); } } printf("%d\n", ans); } return 0; }

转载于:https://www.cnblogs.com/KirinSB/p/11248669.html