[SCOI2015]小凸玩矩阵

题目

题目

做法

很明显的一个事情,求第(K)大的最小值,一般采用的做法是二分(有人会问,但是不满足二分性啊,接着往下看)。

考虑二分答案,但是如何检验(mid)是对还是错,考虑每次只能取(<=mid)的数字,如果能取到((n-k)+1)个数字以上就可以,至于看能否取到(n-k+1)个,采用二分图匹配,左边的点是行,右边的点是列,一个格子能被取,就把其行和列连边。

为什么可以满足二分性,他们认为不满足二分性就只有一个原因,如果我们假定的第(k)大的数字太大的话,可能根本取不到(k)个大于等于这个数字的格子,但是可以取到(n-k+1)个以上小于等于这个数字的格子。

但是我们从函数的角度来证明。

我们设当我们假定的第(k)大的数字为(t)时,小于等于(t)的格子最多取(f(t))个。

那么很明显(f(t)≤f(t+1)),那么如果(f(t-1)<n-k+1,f(t)≥n-k+1),那么(t)就是答案。

(f(t-1))最多取(n-k)个,同时(f(t)≥n-k+1),取(f(t))个小于等于(t)的格子,(n-f(t))个大于(t)的格子,此时第(k)大数小于等于(t),且因为(f(t-1)≠f(t)),所以存在(t)的格子且为第(k)大,所以构造出了第(k)大为(t)的方案。

所以只要存在(f(t-1)<n-k+1,f(t)≥n-k+1),就可以构造出第(k)(t)的方案。

现在证明假如存在最小答案(t),其一定满足(f(t-1)<n-k+1,f(t)≥n-k+1),首先,(f(t))不用证明了(显然),但是(f(t-1))吗,首先如果(f(t-1)≥n-k+1),则一定存在(i)使得(f(i)<n-k+1)(i<t-1)且使得(∀i<j≤t-1,f(j)>=n-k+1),这样(i+1)也是答案,但是(i+1<t),矛盾,得证。

且由于(f(i)≤f(i+1)),简单来说就是找唯一一个满足(f(t-1)<n-k+1,f(t)≥n-k+1)的位置,可以直接二分。

#include<cstdio>
#include<cstring>
#define  N  310
#define  NN  130000
using  namespace  std;
inline  int  mymax(int  x,int  y){return  x>y?x:y;}
inline  int  mymin(int  x,int  y){return  x<y?x:y;}
int  val[N][N],n,m,K,floor_limit,ceil_limit;

bool  ma[N][N],v[N];
int  match[N];
bool  find_match(int  x)
{
	v[x]=1;
	for(int  i=1;i<=m;i++)
	{
		if(!ma[x][i])continue;
		if(!match[i]  ||  (!v[match[i]]  &&  find_match(match[i]))){match[i]=x;return  1;}
	}
	return  0;
}
bool  pd(int  k)
{
	memset(ma,0,sizeof(ma));
	for(int  i=1;i<=n;i++)
	{
		for(int  j=1;j<=m;j++)
		{
			if(val[i][j]<=k)ma[i][j]=1;
		}
	}
	memset(match,0,sizeof(match));
	int  ans=0;
	for(int  i=1;i<=n;i++)
	{
		memset(v,0,sizeof(v));
		ans+=find_match(i);
	}
	return  ans>=(n-K+1);
}
int  main()
{
	scanf("%d%d%d",&n,&m,&K);
	floor_limit=1;ceil_limit=1;
	for(int  i=1;i<=n;i++)
	{
		for(int  j=1;j<=m;j++)
		{
			scanf("%d",&val[i][j]);
			ceil_limit=mymax(ceil_limit,val[i][j]);
		}
	}
	int  l=floor_limit,r=ceil_limit,mid,ans=ceil_limit;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(pd(mid)==1)ans=mid,r=mid-1;
		else  l=mid+1;
	}
	printf("%d
",ans);
	return  0;
}
【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/zhangjianjunab/p/13820322.html