1619D New Year‘s Problem

本文主要是介绍1619D New Year‘s Problem，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：New Year's Problem

从题目的描述中很容易看出来这是一道二分的题目，那么怎么去考虑呢？首先最多选n-1个商店，那也就是说至少有一个商店要选两个人或以上，因此我们的check函数可以去一个个枚举商店，看看是否有一个商店满足两个人，然后每个人选的价值都要大于mid。

代码附上：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
int n,m;
vector<int>a[N];bool check(int mid){for(int i=0;i<n;i++){int t=1;for(int j=1;j<=m;j++){if(a[j][i]>=mid)t=0;}if(t){return false;}}for(int i=1;i<=m;i++){int cnt=0;for(int j=0;j<n;j++){if(a[i][j]>=mid)cnt++;}if(cnt>=2)return true;}return false;}void solve(){cin>>m>>n;for(int i=1;i<=m;i++)a[i].clear();for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){int x;cin>>x;a[i].push_back(x);}}int l=1,r=1e9+5;while(l<r){int mid=l+r+1>>1;if(check(mid))l=mid;else r=mid-1;}cout<<l<<"\n";}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}

这篇关于1619D New Year‘s Problem的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---