题目链接：http://codeforces.com/problemset/problem/15/D
There is an area map that is a rectangular matrix n × m, each cell of the matrix contains the average height of a corresponding area part. Peter works for a company that has to build several cities within this area, each of the cities will occupy a rectangle a × b cells on the map. To start construction works in a particular place Peter needs to remove excess ground from the construction site where a new city will be built. To do so he chooses a cell of the minimum height within this site, and removes excess ground from other cells of the site down to this minimum level. Let's consider that to lower the ground level from h2 to h1 (h1 ≤ h2) they need to remove h2 - h1 ground units.
Let's call a site's position optimal, if the amount of the ground removed from this site is minimal compared to other possible positions. Peter constructs cities according to the following algorithm: from all the optimum site's positions he chooses the uppermost one. If this position is not unique, he chooses the leftmost one. Then he builds a city on this site. Peter repeats this process untill he can build at least one more city. For sure, he cannot carry out construction works on the occupied cells. Would you, please, help Peter place cities according to the algorithm?
Input
The first line contains four space-separated integers: map sizes n, m and city sizes a, b (1 ≤ a ≤ n ≤ 1000, 1 ≤ b ≤ m ≤ 1000). Then there follow n lines, each contains m non-negative space-separated numbers, describing the height matrix. Each number doesn't exceed 109.
Output
In the first line output k — the amount of constructed cities. In each of the following k lines output 3 space-separated numbers — the row number and the column number of the upper-left corner of a subsequent construction site, and the amount of the ground to remove from it. Output the sites in the order of their building up.
Examples
2 2 1 2
1 2
3 5
2
1 1 1
2 1 2
4 4 2 2
1 5 3 4
2 7 6 1
1 1 2 2
2 2 1 2
3
3 1 2
3 3 3
1 2 9
题目大意：
题意：给定n*m的矩阵，每个点都是一个地基，上面的数字表示该地基的高度。
再给定a*b的小房子，要把a*b放在这个矩阵上，显然建房子要保证选取的地基高度一致。
若不一致，则要把选取的a*b大的矩阵中所有地基都挖低使得和其中一块最矮的地基高度一样，花费是挖的高度和
操作：
选取当前花费最小的一块矩阵，在上面建房子，若有多个方案花费一样，则优先选左上角的。一直到不能建房子为止
问：
建的房子的左上角坐标和建该房子的花费
思路：难点在于怎么在不超时的情况下求出所有a*b的矩形内的最小值，这一点可以使用单调双端队列实现：
先求出行范围内的最小值，再求出列的最小值，就出来了，再把结果放入优先队列弹出即可
看代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> #include<map> #include<queue> #include<cmath> using namespace std; typedef long long LL; typedef unsigned long long ull; #define sc1(a) scanf("%lld",&a) #define pf1(a) printf("%lld ",a) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const LL INF=1e18; const ull base=2333; const int maxn=1e3+50; const int maxm=1e3+50; const int maxv=1e6+5; const int mod=1e9+7; const int ba=3e5; LL N,M,A,B; LL a[maxn][maxn]; LL sum[maxn][maxn]; LL mi[maxn][maxn];//存以i j结尾的a*b矩形的最小值 LL x[maxn],y[maxn];//临时数组 求行或者列的区间内的最小值 以i为结尾代表的区间最小值 bool vis[maxn][maxn]; struct Node { LL x,y,mi; Node(){} Node(LL x1,LL y1,LL mi1) { x=x1;y=y1;mi=mi1; } bool operator <(const Node &node) const { if(node.mi==mi) { if(node.x==x) return node.y<y; return node.x<x; } else return node.mi<mi; } }; priority_queue<Node>q; void cal_mi(LL len,LL n) { deque<LL>q;//存下标 for(LL i=1;i<=n;i++) { //维护单调递增队列 并且在区间内 while(!q.empty()&&q.front()+len<=i) q.pop_front();//非空 并且 第一个下标+长度<=i代表第一个下标不包含在i代表的区间内 while(!q.empty()&&x[q.back()]>=x[i]) q.pop_back();//维护单调递增 q.push_back(i); y[i]=x[q.front()]; } } void solve() { vector<Node>ans; ans.clear(); while(!q.empty()) { Node tmp=q.top();q.pop(); LL x1=tmp.x,x2=tmp.x+A-1,y1=tmp.y,y2=tmp.y+B-1; if(vis[x1][y1]||vis[x1][y2]||vis[x2][y1]||vis[x2][y2]) continue; ans.push_back(tmp); for(int i=x1;i<=x2;i++) { for(int j=y1;j<=y2;j++) vis[i][j]=true; } } LL len=ans.size(); pf1(len); for(int i=0;i<len;i++) printf("%lld %lld %lld ",ans[i].x,ans[i].y,ans[i].mi); } int main() { sc1(N);sc1(M);sc1(A);sc1(B); for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { sc1(a[i][j]); sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; } } for(int i=1;i<=N;i++)//此时mi[i][j]求出来的是第i行以j为结尾长度为M的最小值 { for(int j=1;j<=M;j++) x[j]=a[i][j]; cal_mi(B,M); for(int j=1;j<=M;j++) mi[i][j]=y[j]; } for(int i=B;i<=M;i++) { for(int j=1;j<=N;j++) x[j]=mi[j][i]; cal_mi(A,N); for(int j=1;j<=N;j++) mi[j][i]=y[j]; } for(int i=A;i<=N;i++) { for(int j=B;j<=M;j++) { q.push(Node(i-A+1,j-B+1,sum[i][j]-sum[i-A][j]-sum[i][j-B]+sum[i-A][j-B]-mi[i][j]*A*B)); } } solve(); return 0; } /** */