[BOJ 11997] Load Balancing (silver)

https://www.acmicpc.net/problem/11997

11997번: Load Balancing (Silver)

Tag : brute force, prefix sum, coordinate compression

 

문제 요약

x,y축에 평행한 직선을 하나씩 그어서 구간을 4개로 분할하는데

이때 가장 많은 소를 포함한 구간의 소의 수를 M이라하고 이 M중 최소를 찾는 문제다.

 

풀이

세그 스위핑같은 뇌절풀이 짜다가 겨우 정신차렸다.

그냥 좌표압축 후 2차원에서 구간합을 구해놓고 x,y에 평행한 직선은 모든 케이스를 다해보면 된다.

 

시간복잡도 : \(O(N^2)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

int N;
int v[1010][1010];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>N;
    vector<int>x(N),y(N),p(N),q(N);
    for(int i=0;i<N;i++){
        cin>>p[i]>>q[i];
        x[i]=p[i];
        y[i]=q[i];
    }
    compress(x);compress(y);
    for(int i=0;i<N;i++){
        int a=lower_bound(all(x),p[i])-x.begin()+1;
        int b=lower_bound(all(y),q[i])-y.begin()+1;
//        cout<<a<<' '<<b<<endl;
        v[a][b]++;
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            v[i][j]+=v[i][j-1]+v[i-1][j]-v[i-1][j-1];
        }
    }
    int ans=1e9;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            int a=v[i][j];
            int b=v[i][N]-v[i][j];
            int c=v[N][j]-v[i][j];
            int d=v[N][N]-b-c-a;
//            if(i==2 and j==2)cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
            rmin(ans,max({a,b,c,d}));
        }
    }
    cout<<ans<<endl;
}