New Year's Problem

问题传送门
https://codeforces.com/contest/1619/problem/D

问题大意

需要从m个商店给n位朋友买礼物，每人一个，从j号商店为i号朋友买礼物，得到joy值为矩阵元素 $ a_{i}{j} $
矩阵A记录的是joy值，m行n列，规定最多只能去n-1个商店买礼物，且最后每一个朋友都会得到一个joy值，求在所有情况下，n个朋友的joy值的最小值最大能为多少。

算法分析

经过一番分析，可以想到这个题目需要用到二分算法。具体怎么用，其实就是之前做过的二分答案。所谓二分答案，就是题目的答案只可能是某一个最大值和最小值之间的一个数，且通过不断地二分，从而确定答案。
模板如下，仅供参考：

int lower=min, upper=max;
int mid, ans;
while(lower<=upper)
{
    mid = lower+(upper - lower)/2;
    if(isOk(mid))
    {
        // 表示当前mid是符合条件的，但是不一定就是最终的答案，还需要从右边较大区间继续取数检验
        ans = mid;
        lower = mid+1;
    }
    else
    {
        // 表示mid值过大了，从左边的区间取
        upper = mid-1;
    }
}

因此，本题的关键就在于，如何确定选中的mid值是符合条件的呢？
根据题意，我们可以得知，其实要满足题意，需要两个条件：

1. 至多去n-1个商店，也就是至少存在一个商店，在其中购买的礼物至少有两个（因为一共买n个礼物）；
2. 每一个朋友有且仅有一个礼物。

所以，在isOk()中，对矩阵进行遍历检验即可。

// 判断两点：
// 1.至少有一个商店，在其中购买至少两件礼物；
// 2.每一个朋友都有且仅有一件礼物
bool isOk(long long x, vector<vector<int>> all)
{
    int flag = 0;
    for (int i = 1; i <= m; i++)
    {
        int num = 0;
        for (int j = 1; j <= n; j++)
        {
            if (all[i][j] >= x)
            {
                num++;
                fri[j] = 1;
            }
        }
        //条件一满足，就置flag标志变量为1，否则一直为0
        if (num >= 2)  flag = 1;
    }
    // 检验条件二，是否每一个朋友都有礼物
    int isAll = 1;
    for (int i = 1; i <= n; i++)
        isAll = isAll && fri[i];
    return isAll && flag;
}

综上，问题得以解决。