[AtCoder2557]Ball Coloring

Posted on | In

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

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

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

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

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

    $O$ $($ $n$ $)$就可以求出红蓝球区间的最大差值的最小值

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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;
}