自动搬运

查看原文

来自洛谷，原作者为

	Unordered_OIer **

搬运于2025-08-24 21:45:44，当前版本为作者最后更新于2020-02-18 20:54:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$