题解 AT2557 【Ball Coloring】

RicardoShips · 2019-01-23 17:15:37 · 题解

不得不说一句，这题在AtCoder里算一道水题

但是我时间空间都被同桌巨佬爆踩，还是水得不行啊

首先分类讨论，假设我们把最大值的球涂成蓝色

• 最小值的球涂成红色，那么我们可以贪心

  把每个袋子里面较大值的球涂成蓝色，较小值的球涂成红色

  但是这样不一定能使$ans$最小，接着来看另一种情况

• 最小值的球也涂成蓝色，这样Bmax - Bmin就已经确定了

  那么我们就要让红球的区间最大差值最小

  所以我们可以在上面的基础上

  按照x从小到大的顺序，把颜色依次翻转

  在翻转的过程中O ( n )求出红球区间的最大差值的最小值

最后我们只要把两种答案再取最小值，就是最后的ans

#include<bits/stdc++.h>
#define INF 1000000007
using namespace std;
struct sakura
{
    long long x;
    long long y;
}
ball[222222];
long long x[222222];
long long y[222222];
long long maxn[222222];
long long minl[222222];
long long n,ans,ans1,ans2,bmax,bmin,rmax,rmin;
inline bool cmp(sakura xx,sakura yy){ return xx.x<yy.x; }
int main()
{
    scanf("%lld",&n);
    bmax=rmax=-1;bmin=rmin=INF;
    for(register int i=1;i<=n;++i)
    {
        scanf("%lld%lld",&x[i],&y[i]);
        if(x[i]>y[i]) swap(x[i],y[i]);
        ball[i].x=x[i];ball[i].y=y[i];
        bmax=max(bmax,y[i]);
        bmin=min(bmin,y[i]);
        rmax=max(rmax,x[i]);
        rmin=min(rmin,x[i]);
    }
    ans1=(bmax-bmin)*(rmax-rmin);
    bmin=rmin;sort(ball+1,ball+n+1,cmp);
    ans2=INF;maxn[1]=minl[1]=ball[1].y;
    for(register int i=2;i<=n;++i)
    {
        maxn[i]=max(maxn[i-1],ball[i].y);
        minl[i]=min(minl[i-1],ball[i].y);
        if(i!=n) ans2=min(ans2,max(maxn[i],ball[n].x)-min(minl[i],ball[i+1].x));
    }
    ans2*=(bmax-bmin);ans=min(ans1,ans2);
    printf("%lld\n",ans);
    return 0;
}