Two-point answer naked question (plus a little pigeonhole principle)

New Year’s Problem （naked dichotomy）

题面翻译

题目描述

Vlad 有 $n$ 个朋友,Every friend needs and only needs $1$ 个礼物.有 $m$ gift shop,如果在第 $i$ friends in stores $j$ 买礼物,朋友 $j$ 将获得 $p_{ij}$ 的快乐值.

由于时间紧迫, Vlad Only at most $n-1$ Buy gifts from different stores.Please make the minimum value of happiness that each friend can get is the largest.

输入格式

第一行一个整数 $t$,表示有 $t$ 组测试数据.

每组测试数据之间有一个空行.对于每组测试数据,第一行两个整数 $m$ 和 $n$.接下来 $m$ 行,每行 $n$ 个整数,其中第 $i$ 行的第 $j$ 个数表示 $p_{ij}$.

保证 $t\le 10^4$,$p_{ij}\le 10^9$,$n\ge 2$,and in all test data $n\cdot m$ 的和不超过 $10^5$.

输出格式

输出 $t$ 行,Each row contains the answer for the corresponding test data,即 Vlad The maximum value of the minimum happiness value among the friends of .

样例 #1

样例输入 #1

5

2 2
1 2
3 4

4 3
1 3 1
3 1 1
1 2 2
1 1 3

2 3
5 3 4
2 5 1

4 2
7 9
8 1
9 6
10 8

2 4
6 5 2 1
7 9 7 2

样例输出 #1

3
2
4
8
2

---

naked dichotomy,Will not judge,That's my code levelshit

1. A store is responsible for at least two items
2. Each person can only buy one item！
3. Everyone has to have items

Two-point answer bare question.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#include<ctime>
#define x first
#define y second
#define debug(x) cout<<#x<<"="<<x<<endl;
using namespace std;

typedef pair<int,int>PII;
typedef long long ll;
const int N = 1e5+10;

int n,m;

bool ck(ll x,vector<vector<int>>g){
    
    set<int>s;
    for(int i=0;i<n;i++){
    
        for(int j=0;j<m;j++){
    
            if(g[j][i] >= x){
    
                s.insert(i);
            }
        }
    }
    bool ok = 0;
    for(int i=0;i<m;i++){
    
        int cnt=0;
        for(int j=0;j<n;j++){
    	
            if(g[i][j] >= x){
    
                cnt++;
            }
        }
        if(cnt>=2){
    
            ok = 1;
        }
    }
    if(!ok || (int)s.size() < n )return 0;
    return 1;
}

void solve(){
    
    cin>>m>>n;
    vector<vector<int>>g(m,vector<int>(n));
    for(int i=0;i<m;i++){
    
        for(int j=0;j<n;j++){
    
            cin>>g[i][j];
        }
    }
    ll  l = 1, r = 1e9+10;
    while(l<r){
    
        ll mid = l+r+1>>1;
        if(ck(mid,g)){
    
            l = mid;
        }
        else{
    
            r = mid-1;
        }
    }
    cout<<l<<endl;

}

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

Doremy’s IQ

题面翻译

题目描述

哆来咪·Suit participated $n$ 场比赛. 比赛 $i$ 只能在第 $i$ 天进行.比赛 $i$ 的难度为 $a_i$.最初,Doremi's IQ 为 $q$ . 在第 $i$ 天,Doremi will choose whether to participate in the competition i.Only if she is current IQ 大于 $0$ 时,She can enter the game.

If Doremi chooses to be in the first $i$ day to participate in the game $i$,则会发生以下情况：

• 如果 $a_i>q$,Doremi will feel that he is not smart enough,所以 $q$ 将会减 $1$;
• 否则,什么都不会改变.

If she chooses not to compete,一切都不会改变.Doremi wants to participate in as many competitions as possible.Please give Doremi a solution.

输入格式

第一行包含一个正整数 $t$ ($1\le t\le 10^4$) ,表示测试数据的组数.

第二行包含两个整数 $n$ 和 $q$ ($1\le n\le 10^5$, $1\le q\le 10^9$),Indicates the number of games and when Doremi started IQ.

第三行包含 $n$ 个整数 $a_1,a_2\cdots a_n$($1\le a_i\le 10^9$),Indicates the difficulty of each game.

数据保证 $n$ 之和不超过 $10^5$.

输出格式

对于每组数据,Output a binary string $s$,If Doremi should choose to participate in the competition $i$,则 $s_i=1$,否则 $s_i=0$. 字符串中 $1$ The number should be as large as possible,and be hers IQ 为 $0$ 或更低时,She shouldn't be in the game.

如果有多个解决方案,You can output either one.

样例说明

在第一个测试用例中,Doremi participated in the only competition.她的 IQ 没有下降.

在第二个测试用例中,Doremi participated in two competitions.在参加比赛 $2$ 后,她的 IQ 下降了 $1$.

在第三个测试用例中,Doremi participated in the competition $1$ 和比赛 $2$.她的 IQ 在参加比赛 $2$ 后降至 $0$,So she couldn't participate in the competition $3$.

样例 #1

样例输入 #1

5
1 1
1
2 1
1 2
3 1
1 2 1
4 2
1 4 3 1
5 2
5 1 2 4 3

样例输出 #1

1
11
110
1110
01111

---

Low IQ warning,I really don't understand how to think about the solution.Duality is not analyzed.
SOLUTION_1
EDITORIAL

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#include<ctime>
#define x first
#define y second
#define debug(x) cout<<#x<<"="<<x<<endl;
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
using namespace std;

typedef pair<int,int>PII;
typedef long long ll;
const int N = 1e5+10;

int n,m;
int a[N];

bool ck(int x){
    
	int w = m;
	fo(i,x+1,n){
    
		if(a[i]>w)w--;
	}
	return w>=0;
}

bool ans[N];
void solve(){
    
    cin>>n>>m;
    fo(i,1,n){
    
        cin>>a[i];
    }
    int l = 0 , r = n; // l 一定要从0开始,不然会wa
    while(l<r){
    
        int mid = l+r>>1;
        if(ck(mid)){
    
           	r = mid;
        }
        else{
    
			l = mid+1;
        }
    }
    
	fo(i,1,n){
    
		if(i<=l){
    
			if(a[i]<=m){
    
				cout<<"1";
			}
			else{
    
				cout<<"0";
			}
		}
		else{
    
			cout<<"1"; 	
		}
	}
	puts("");
}


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