[CodeForces]529B Group Photo 2

AK爷GhostCai的电脑又蓝屏了Orz

贪心题，确定一个maxh，限定h不大于一个值。枚举maxh。

check的时候的细节很多：

1.h>maxh但w<maxh交换的时候需要占用交换名额。

2.cnt<0了就应该return -1了。。。

突然忘记还有啥细节

代码如下

#include <iostream>

#include <algorithm>

#include <cstdio>

using namespace std;

const int N=1005;

int n,w[N],h[N],maxh,ans=0x3f3f3f3f;

bool cmp(int x,int y) {return x>y;}

int ck(int mxh) {

	int tp=0,diff[N],cnt=n/2;

	for(int i=1;i<=n;i++) {

	if(h[i]>mxh&&w[i]>mxh) return -1;

	if(h[i]>mxh&&w[i]<=mxh) diff[i]=-1,tp+=h[i],cnt--;

	else if(w[i]>mxh) diff[i]=-1,tp+=w[i];

	else diff[i]=w[i]-h[i],tp+=w[i];

	}

	if(cnt<0) return -1;

	sort(diff+1,diff+1+n,cmp);

	for(int i=1;i<=cnt;i++) {

		if(diff[i]>0) tp-=diff[i];

		else break;

	}

	return tp*mxh;

}

int main() {

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&h[i]),maxh=max(maxh,h[i]);

	for(int i=1;i<=1000;i++) {

		int t=ck(i);

		if(t==-1) continue;

		ans=min(ans,t);

	}

	cout<<ans;

}

巴特西

[CodeForces]529B Group Photo 2

最新文章

热门文章