CFS-Round-762 D.New Year‘s Problem 题解 (二分+贪心)

• • 1 题意
  • • 1.1 原文
    • 1.2 题目简意
  • 2 思路
  • • 2.1 二分
    • 2.2 贪心

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.

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

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

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

  算法复杂度： O ( N ∗ M ∗ l o g ( 1 e 9 ) ) O(N*M*log(1e9)) O(N∗M∗log(1e9))

  参考代码

#include 
using namespace std;
const int N = 1e5 + 10;
int m, n ;
bool st[N];

bool check(int mid, vector> &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 > s(m, vector(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< 
2.2 贪心 
  这题贪心的核心难点在于要送 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个朋友，但只能去 
    
     
      
       
        n
       
       
        −
       
       
        1
       
      
      
       n-1
      
     
    n−1 个商店。要找最小值的最大值，要分为两种情况。
 
State1: 
    
     
      
       
        n
       
       
        −
       
       
        1
       
       
        ≥
       
       
        m
       
      
      
       n - 1 ≥ m
      
     
    n−1≥m ，此时可以选 
    
     
      
       
        n
       
       
        −
       
       
        1
       
      
      
       n-1
      
     
    n−1 个商店，但实际上的商店数量也不超过 
    
     
      
       
        n
       
       
        −
       
       
        1
       
      
      
       n-1
      
     
    n−1，故我们要参与选择礼物的商店就是所有商店。这个时候要求答案就很简单了，只需贪心地为每一个朋友选择能获得最大快乐值的商店（每一列的最大值）购买礼物，然后求其最小值就可以，设此时最小值为 joy_min。
 
State2: 
    
     
      
       
        n
       
       
        −
       
       
        1
       
       
        <
       
       
        m
       
      
      
       n - 1 < m
      
     
    n−1 
  算法复杂度：
    
     
      
       
        O
       
       
        (
       
       
        N
       
       
        ∗
       
       
        M
       
       
        )
       
      
      
       O(N*M)
      
     
    O(N∗M)
 
  参考代码
 
#include 
using namespace std;
void solveD()
{
    int t;
    cin >> t;
    while (t--)
    {
        int m, n;
        cin >> m >> n;
        vector > 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 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 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)<