CodeForces 1619D New Year's Problem

题目链接：CodeForces 1619D【New Year's Problem】

思路

       可以因为最多只能逛n - 1个商店，当n - 1大于等于m的时候，所有朋友都能取最大值，否则至少有两个人要选择相同的商店，所以依次枚举两个人选择同一个商店，其他人选择喜悦值最大的商店。

代码

#include <cstddef>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
const int N = 2e5 + 10;

ll a[N], num[N], maxn[N];

void solve() {
  memset(num, 0, sizeof num);
  memset(maxn, 0, sizeof maxn);

  // n is the number of friend 
  int n, m;
  cin >> m >> n;
  vector<vector<ll>> ve(m + 1, vector<ll>(n + 1));
  
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> ve[i][j];
      maxn[j] = max(maxn[j], ve[i][j]);
    }
  }
  ll minn = 1e9;
  for (int i = 1; i <= n; i++) {
    minn = min(minn, maxn[i]);
  }


  ll res = 0; 
  if (n - 1 >= m) {
    res = minn;
  } else {
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        for (int k = j + 1; k <= n; k++) {
          // 选两个人在同一个商店买礼物
          res = max(res, min(minn, min(ve[i][j], ve[i][k])));
        }
      }
    }
  }
  cout << res << endl;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }

  return 0;
}