[数据结构与算法]CFS-Round-762 D.New Year‘s Problem 题解 (二分+贪心)

1 题意

1.1 原文

Vlad has 𝑛 friends, for each of whom he wants to buy one gift for the New Year.

There are 𝑚 shops in the city, in each of which he can buy a gift for any of his friends. If the 𝑗-th friend (1≤𝑗≤𝑛) receives a gift bought in the shop with the number 𝑖 (1≤𝑖≤𝑚), then the friend receives 𝑝𝑖𝑗 units of joy. The rectangular table 𝑝𝑖𝑗 is given in the input.

Vlad has time to visit at most 𝑛?1 shops (where 𝑛 is the number of friends). He chooses which shops he will visit and for which friends he will buy gifts in each of them.

Let the 𝑗-th friend receive 𝑎𝑗 units of joy from Vlad’s gift. Let’s find the value 𝛼=min{𝑎1,𝑎2,…,𝑎𝑛}. Vlad’s goal is to buy gifts so that the value of 𝛼 is as large as possible. In other words, Vlad wants to maximize the minimum of the joys of his friends.

For example, let 𝑚=2, 𝑛=2. Let the joy from the gifts that we can buy in the first shop: 𝑝11=1, 𝑝12=2, in the second shop: 𝑝21=3, 𝑝22=4.

Then it is enough for Vlad to go only to the second shop and buy a gift for the first friend, bringing joy 3, and for the second — bringing joy 4. In this case, the value 𝛼 will be equal to min{3,4}=3
Help Vlad choose gifts for his friends so that the value of 𝛼 is as high as possible. Please note that each friend must receive one gift. Vlad can visit at most 𝑛?1 shops (where 𝑛 is the number of friends). In the shop, he can buy any number of gifts.

Input
The first line of the input contains an integer 𝑡 (1≤𝑡≤1e4) — the number of test cases in the input.

An empty line is written before each test case. Then there is a line containing integers 𝑚 and 𝑛 (2≤𝑛, 2≤𝑛?𝑚≤1e5) separated by a space — the number of shops and the number of friends, where 𝑛?𝑚 is the product of 𝑛 and 𝑚.

Then 𝑚 lines follow, each containing 𝑛 numbers. The number in the 𝑖-th row of the 𝑗-th column 𝑝𝑖𝑗 (1≤𝑝𝑖𝑗≤1e9) is the joy of the product intended for friend number 𝑗 in shop number 𝑖.

It is guaranteed that the sum of the values 𝑛?𝑚 over all test cases in the test does not exceed 1e5.

Output
Print 𝑡 lines, each line must contain the answer to the corresponding test case — the maximum possible value of 𝛼, where 𝛼 is the minimum of the joys from a gift for all of Vlad’s friends.

1.2 题目简意

?? 有 $n$ 个朋友、$m$ 个商店，输入一个二维数组 $p$ , 其中第 $i$ 个商店买的商品送给第 $j$ 个朋友可以使该朋友收获 $p_{i,j}$ 的快乐值，但是只能选择 $n?1$ 个商店从中买礼物，每个朋友送一件礼物。
?? 这样一来可以假设第 $i$ 个朋友能收到 $a_i$ 的快乐值。要求输出 min{$a_1,a_2...a_n$} 的最大值。

2 思路

2.1 二分

?? 这题如果用二分，那应该是比较容易出思路的。假设我们二分到答案为mid，这个时候根据矩阵 $p$可以构造一个辅助矩阵 $st$,使得
$$st[i][j]=\{\begin{array}{ll}0& \text{mid≤p[i][j]}\\ 1& \text{mid>p[i][j]}\end{array}$$

??在对当前mid的check中，对于这样一个辅助矩阵 $st$ ，如果每一列都有1存在，并且至少有一行拥有两个1，则这个mid可行，可以再往后二分，否则不可行，往前二分。

??算法复杂度：$O(N?M?log(1e9))$

??参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int m, n ;
bool st[N];

bool check(int mid, vector<vector<int>> &s) {
	bool w1 = false;
	for(int i=0,i<=m - 1;i++) st[i] = false;
	for(int j=0,j<=n - 1j++) {
		bool w2 = false;
		for(int i=0,i<=m - 1;i++) {
			if (s[i][j] >= mid) {
				if (st[i])
					w1 = true;
				else
					st[i] = true;
				w2 = true;
			}
		}
		if (!w2)
			return 0 ;
	}
	return w1;
}

int main() {

	int t;
  cin >> t;
  while (t--)
  {
		cin>>m>>n;
		vector<vector<int> > s(m, vector<int>(n)) ;
		for(int i=0, i<=m - 1;i++){
    	for(int j=0, j<=n - 1;j++) cin>>s[i][j];
    } 
		int l = 1, r = 1e9 ;
		while (l < r) {
			int mid = r + l + 1 >> 1 ;
			if (check(mid, s))
				l = mid ;
			else
				r = mid - 1 ;
		}
		cout<<l<<endl;
	}
	return 0;
}

2.2 贪心

??这题贪心的核心难点在于要送 $n$ 个朋友，但只能去 $n?1$ 个商店。要找最小值的最大值，要分为两种情况。

State1: $n?1\ge m$ ，此时可以选 $n?1$ 个商店，但实际上的商店数量也不超过 $n?1$，故我们要参与选择礼物的商店就是所有商店。这个时候要求答案就很简单了，只需贪心地为每一个朋友选择能获得最大快乐值的商店（每一列的最大值）购买礼物，然后求其最小值就可以，设此时最小值为 joy_min。

State2: $n?1<m$ ,此时需要考虑的商店数量超过了可实际选择购买的商店数量，应题目要求，我们要先确定去哪 $n?1$个商店进行购买。这个时候就必定有一家商店，使我们在这家店至少会为两个朋友购买礼物。设每个商店的次大快乐值为joy_smax，那么这个时候答案必定是不会大于joy_smax的。接下来还剩下 $n?2$ 个商店和 $n?2$ 个朋友，这些选择的思路和state1中的情况一样。故答案就是min{joy_smax,joy_min}。

??算法复杂度：$O(N?M)$

??参考代码

#include <bits/stdc++.h>
using namespace std;
void solveD()
{
    int t;
    cin >> t;
    while (t--)
    {
        int m, n;
        cin >> m >> n;
        vector<vector<int> > p(m);
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int tp;
                cin >> tp;
                p[i].push_back(tp);
            }
        }
        vector<int> maxp(n);
        int minn = 0x3f3f3f3f;  // 每一列的最大值 的最小值
        int maxx = 0;  // 每一行的次大值 的 最大值
        for (int j = 0; j < n; j++)
        {
            maxp[j] = 0;
            for (int i = 0; i < m; i++)
            {
                maxp[j] = max(maxp[j], p[i][j]);  // 每一列的最大值
            }
            minn = min(minn, maxp[j]);  
        }
        for(int i =0;i<m;i++){
            
            vector<int> vtp = p[i];
            sort(vtp.begin(),vtp.end());
            maxx = max(maxx,vtp[n-2]);
        }

        if (n - 1 >= m)  // 如果friend数足够多，那就不需要考虑怎么选择商店最合适，直接每个friend都去选择对与他们最好的商店即可，也就是直接求minn
        {
            cout << minn << endl;
        }
        else{
            cout << min(minn,maxx)<<endl;  // 必有一个商店需至少承担俩个购买量，该商店的次大值必将是拉低joy的可能因素，与上一种情况的最小值一起求min即可
        }
    }
}

int main()
{
    solveD();
    return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖