codechef [snackdown2017 Onsite Final] Minimax

题目描述

　　考虑一个 N 行 N 列的网格，行列编号均为 1 ∼ N。每个格子中包含一个整数。记 ri 为第 i 行的最小值，Ci 为第 i 列的最大值。我们称一个网格为好的，当且仅当满足：$$max(r1, . . . , rN ) = min(C1, . . . , CN )$$

　　大厨有这么一个网格，他可以将格子中的数字改为任意整数。请你告诉大厨，他至少需要改变几个数字，才能使得网格变成好的。

输入格式

　　输入第一行，包含一个整数 N，代表网格的边长。接下来 N 行，每行包含 N 个整数，代表每个格子中的整数。

输出格式

　　输出一个整数，代表最少需要改变的数字个数。

　　这是Easy难度题啊qaq，那我大概只能回去刷beginner了。

　　如果枚举一个最终k=max(ri)=max(li)，那么代价就是一行内小于k的数字最少的数字数量加上一列内大于k的数字最少的数字数量，这样直接暴力是$O(n^4)$的。

　　然后窝尝试三分k的值（因为看起来是单峰的嘛），结果好像并不行……

　　回到暴力看一下，咦，这不是可以用堆优化一下嘛……复杂度$O(n^{2}logn)$

被人看着写博客催颓废是一种什么样的感受……

#include<queue>

#include<cstdio>

#include<cassert>

#include<algorithm>

#define fi first

#define se second

#define mp make_pair

#define MN 1100

using namespace std;

struct na{int x,y;}p[];

int n,a[MN][MN],MMH=1e9,num=,r[MN],c[MN];

bool operator < (na x,na y){return a[x.x][x.y]<a[y.x][y.y];}

priority_queue<pair<int,int> > R,C;

int main(){

    scanf("%d",&n);

    for (int i=;i<=n;i++) c[i]=n;

    for (int i=;i<=n;i++)

    for (int j=;j<=n;j++)

    scanf("%d",&a[i][j]),p[++num].x=i,p[num].y=j;

    sort(p+,p++num);

    for (int i=;i<=n;i++) R.push(mp(,i)),C.push(mp(-n,i));

    int _L=,_R=;

    for (int k=;k<=;k++){

        while (a[p[_R].x][p[_R].y]==k&&_R<=num) _R++;

        for (int i=_L;i<_R;i++) c[p[i].y]--,C.push(mp(-c[p[i].y],p[i].y));

        while (C.top().fi!=-c[C.top().se]) C.pop();

        while (R.top().fi!=-r[R.top().se]) R.pop();

        if (-C.top().fi-R.top().fi<MMH) MMH=-C.top().fi-R.top().fi;

        for (int i=_L;i<_R;i++) r[p[i].x]++,R.push(mp(-r[p[i].x],p[i].x));

        _L=_R;

    }

    printf("%d\n",MMH);

}