codeforces 15D . Map 优先队列

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接

题目意思很简单nm的矩阵里， 选若干个ab的小矩阵， 定义每个矩阵的值为这个矩阵里的所有数的和-最小值*数的个数。



选小矩阵时， 优先选值最小的，然后次小的.. 知道不能选位置。

输出所有矩阵的左上角那个数的坐标以及这个矩阵的值。

思路很简单， 将所有矩阵的值加到一个优先队列里面， 然后一个一个的删除。 直到矩阵空。

不好做的是求一个矩阵中的最小值。 我先是用二维线段树， tle。 然后用二维st表， mle....

然后看cf上的代码 ，用一个multiset来搞。 具体看代码..

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <complex>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef complex <double> cmx;
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int mod = 1e9+7;
const int inf = 1061109567;
const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
const int maxn = 1002;
int vis[maxn][maxn], n, m, c[maxn][maxn], d[maxn][maxn];
ll sum[1002][1002];
struct node
{
ll val;
int x, y;
bool operator < (node a) const{
if(val != a.val)
return val>a.val;
if(x != a.x)
return x>a.x;
return y>a.y;
}
node() {}
node(ll _val, int _x, int _y):val(_val), x(_x), y(_y){}
};
vector <node> ans;
int main()
{
int a, b;
priority_queue <node> q;
cin>>n>>m>>a>>b;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%I64d", &sum[i][j]);
c[i][j] = sum[i][j];
}
}
for(int i = 1; i <= n; i++) {
multiset <int> tmp;
for(int j = 1; j <= m; j++) {
if(j>b) {
tmp.erase(tmp.find(c[i][j-b]));
}
tmp.insert(c[i][j]);
d[i][j] = *(tmp.begin());
}
}
for(int j = 1; j <= m; j++) {
multiset <int> tmp;
for(int i = 1; i <= n; i++) {
if(i>a) {
tmp.erase(tmp.find(d[i-a][j]));
}
tmp.insert(d[i][j]);
c[i][j] = *(tmp.begin());
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
sum[i][j] += sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
}
for(int i = 1; i <= n-a+1; i++) {
for(int j = 1; j <= m-b+1; j++) {
int x = i+a-1;
int y = j+b-1;
ll num = sum[x][y]-sum[i-1][y]-sum[x][j-1]+sum[i-1][j-1];
ll res = num - 1LL*c[x][y]*a*b;
q.push(node(res, i, j));
}
}
while(!q.empty()) {
node tmp = q.top(); q.pop();
if(vis[tmp.x][tmp.y])
continue;
ans.pb(tmp);
for(int i = max(1, tmp.x-a+1); i <= min(tmp.x+a-1, n); i++) {
for(int j = max(tmp.y-b+1, 1); j <= min(tmp.y+b-1, m); j++) {
vis[i][j] = 1;
}
}
}
cout<<ans.size()<<endl;
sort(ans.begin(), ans.end());
reverse(ans.begin(), ans.end());
for(int i = 0; i < ans.size(); i++) {
printf("%d %d %I64d\n", ans[i].x, ans[i].y, ans[i].val);
}
return 0;
}