题解 P3933 【Chtholly Nota Seniorious】

Anoxiacxy · 2017-10-21 16:17:39 · 题解

对于这种最优化问题，我们可以二分答案啊，显然，最大值和最小值一定不被划分到一个区域里，那么我们假定最大值在矩形的上三角里，对于那些大于最大值减去我们二分的答案的数，都是符合要求的，然后判断不在当前区域的数，是不是都小于最小值加上我们二分的答案，由于最大值，最小值的位置不确定，所以我们可以把矩阵旋转四次，分别判断即可，只要有一种满足条件即可

以下为英语短文填空裸题，后附参考答案

#include <cstdio>
#include <cstring>
#include <iostream>
#define inf int(2e9)
#define nl NULL
using namespace std;
int ___,____;int ______________=0,_____________=inf;
int _________________[4][2017][2017],_______________=3;
bool __________________[2017][2017];
void ________(int ___________________,int ____________________){
    for(int _=1;_<=___;_++)
        for(int __=1;__<=____;__++)
            _________________[____________________][__][___-_ + 1]=_________________[___________________][_][__];
    swap(____ ,___);
}
bool _________(int ________________){
    int ____________=____;
    memset(__________________,0,sizeof(__________________));
    for(int _=1;_<=___;_++)
        for(int __=1;__<=____________;__++)
            if(_________________[_______________][_][__]+________________<______________){
                ____________=__-1;break;
            }else __________________[_][__] = true;
    for(int _=___;_; _--)
        for(int __=____; __; __--)
            if(__________________[_][__])break;
            else if(_________________[_______________][_][__]-________________>_____________)return false;
    return true;
}
void ___________(){swap(___,____);_______________=(_______________+1)%4;}
bool __________(int ________________){
    if(_________(________________)) return true; ___________();
    if(_________(________________)) return true; ___________();
    if(_________(________________)) return true; ___________();
    if(_________(________________)) return true; ___________();
    return false;        
}
int main(){
    scanf("%d%d",&___,&____);
    for(int _=1;_<=___;_++)for(int __=1;__<=____;__++){
        scanf("%d",&_________________[0][_][__]);
        ______________=max(______________,_________________[0][_][__]);
        _____________=min(_____________,_________________[0][_][__]);
    }
    ________(0,1);________(1,2);________(2,3);
    int _____=0,______=______________-_____________;
    while(_____<______){
        int _______=_____+______ >> 1;
        if(__________(_______))______=_______;
        else _____=_______+1;
    }
    printf("%d",_____);
}

参考答案

#include <cstdio>
#include <cstring>
#include <iostream>
#define inf int(2e9)
#define nl NULL
using namespace std;
int n,m;int maxv = 0, minv = inf;
int a[4][2017][2017], coc = 3;
bool f[2017][2017];
void rotate(int s,int t){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            a[t][j][n - i + 1] = a[s][i][j];
    swap(m ,n);
}
bool deal(int ans){
    int p = m;
    memset(f, 0, sizeof(f));
    for(int i = 1; i<= n; i++)
        for(int j = 1; j <= p; j++)
            if(a[coc][i][j] + ans < maxv){
                p = j - 1; break;
            }else f[i][j] = true;
    for(int i = n; i; i--)
        for(int j = m; j; j--)
            if(f[i][j]) break;
            else if(a[coc][i][j] - ans > minv) return false;
    return true;
}
void nxt() {swap(n, m); coc = (coc + 1) % 4; }
bool check(int ans){
    if(deal(ans)) return true;nxt();
    if(deal(ans)) return true;nxt();
    if(deal(ans)) return true;nxt();
    if(deal(ans)) return true;nxt();
    return false;        
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        scanf("%d",&a[0][i][j]);
        maxv = max(maxv, a[0][i][j]);
        minv = min(minv, a[0][i][j]);
    }
    rotate(0, 1); rotate(1, 2); rotate(2, 3);
    int l = 0, r = maxv - minv;
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d", l);
}