萌新不会二分求助!
查看原帖
萌新不会二分求助!
631787
Watanabe楼主2023/10/23 07:56

第二个点就t了,瞪不出来哪里写寄了

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#define re register
#define int long long

using namespace std;
const int N=1e5+100;
int T,n,m;
vector <int> p[N];
int w,ans;

bool v[N];
bool g[N];
int s[N],tot;
int cnt[N];
inline bool check(int x)
{
	memset(v,0,sizeof v);
	memset(cnt,0,sizeof cnt);
	for(re int i=1;i<=m;++i) 
	{
		tot=0;
		for(re int j=0;j<n;++j)
		{
			if(p[i][j]>=x) 
			{
				v[j+1]=true ;
				if(!g[j+1]) 
				{
					s[++tot]=j+1;
					g[j+1]=true ;
					++cnt[i];
				}
			}
		}
		while(tot)
		{
			g[s[tot--]]=false ;
		}
	}
	for(re int i=1;i<=n;++i) 
	{
		//if(!v[i]) cout<<x<<" "<<i<<"\n";
		if(!v[i]) return false ;
	}
	for(re int i=1;i<=m;++i) if(cnt[i]>1) return true ;
	return false ;
	
}
int l,r;
signed main()
{
	cin>>T;
	while(T--)
	{
		cin>>m>>n;
		for(re int i=1;i<=m;++i)
		{
			p[i].clear();
			for(re int j=1;j<=n;++j)
		    {
		  	    cin>>w;
		  	    p[i].push_back(w);
		    }
		}
		  
		l=1,r=1e9+1;
		while(l<=r)
		{
			int mid=l+r>>1;
			if(check(mid)) ans=mid,l=mid+1;
			else r=mid-1;
		}
		cout<<ans<<"\n";
	}
	return 0;
}
/*

*/
2023/10/23 07:56
加载中...