题解 P3142 【[USACO16OPEN]Field Reduction S】

· · 题解

P3142 题解

        ——————————一篇为新手村准备的题解

大致思路是一样的，就是暴力枚举删除每一头牛的情况。但是我看了一下，有dalao的题解中的代码本新手认为不是非常易懂，于是诞生了这篇为新手提供的代码。
思路：直接正面进攻这一题，似乎不是那么好做。那么我们就瞄准一个重要的条件：卖掉三只牛。

“三”只牛，这个数据实在是太小了，我们只需要暴力枚举最优的情况，就行了。但是怎么确定围栏的面积呢？

我们知道，围栏是一个矩形，矩形的面积计算是长×宽，那么问题就变为怎么确定长和宽？

这个问题实际上就非常好解决了，我们只需要确定maxx-minx与maxy-miny，就对应了长与宽。那么面积问题解决了，还有一个问题：如果数据较小，容易出现一头牛删了两次的情况。

怎么解决呢？很简单，使用一个数组记录每头牛的“id”，然后使用这个“id”进行循环就行了。
(本人觉得标记数组的方法有些像分块或者离散化)

这里切记切记，必须要按x,y分别写cmp函数，混了之后就不对了。

这里需要注意，设无穷大的值的时候一定要设精确，因为输出的最大值我们可以估算一下，题目数据给的是40000，计算面积少不了平方，就是40000^2=1.6*10^9=1600000000
所以我们在设定的时候最好要大于这个值，设2e10是最方便的，本人在这里被坑了好多次。

最后安利一下我的blog

#include<bits/stdc++.h>
#define N 50005
#define INF 2e10
using namespace std;
typedef long long ll;
struct Cow{ll x,y;}a[N];
ll n,b[N],c[N],d[N],ans=INF;
bool cmp1(ll x,ll y){
    return a[x].x<a[y].x || (a[x].x==a[y].x && a[x].y<a[y].y);
}
bool cmp2(ll x,ll y){
    return a[x].y<a[y].y || (a[x].y==a[y].y && a[x].x<a[y].x);
}
void work(ll x,ll y,ll z){
    memset(d,0,sizeof(d));
    for (ll i=1; i<=x; i++) d[b[i]]=1;
    for (ll i=1; i<=y; i++) d[b[n-i+1]]=1;
    //
    ll m=0;
    for (ll i=1; i<=n; i++)
        if (!d[i]) c[++m]=i;
       //标记数组
    sort(c+1,c+m+1,cmp2);//排序
    for (ll i=1; i<=z; i++) d[c[i]]=1;
    for (ll i=1; i+x+y+z<=3; i++) d[c[m-i+1]]=1;//用标记数组标记d
    ll mxx=0,mxy=0,mix=INF,miy=INF;
    for (ll i=1; i<=n; i++)
        if (!d[i]){
            mxx=max(maxx,a[i].x);
            mix=min(minx,a[i].x);
            mxy=max(maxy,a[i].y);
            miy=min(miny,a[i].y);
        }//标记端点
    if (mxx<=mix || mxy<=miy) ans=0;
    else ans=min(ans,(mxx-mix)*(mxy-miy));
    //计算面积
}
int main(){
    scanf("%lld",&n);
    for (ll i=1; i<=n; i++) scanf("%lld%lld",&a[i].x,&a[i].y);
    for (ll i=1; i<=n; i++) b[i]=i;//注意要标记好b
    sort(b+1,b+n+1,cmp1);//b要按cmp1排序
    for (ll i=0; i<=3; i++)
        for (ll j=0; i+j<=3; j++)
            for (ll k=0; i+j+k<=3; k++)
                work(i,j,k);//暴力
    printf("%lld\n",ans);//输出
    return 0;
}

本人的一篇良心题解，望管理员给过吧。

update:2020-02-18