二分答案裸题（加一点鸽巢原理）

New Year’s Problem （裸二分）

题面翻译

题目描述

Vlad 有 $n$ 个朋友，每个朋友需要且仅需要 $1$ 个礼物。有 $m$ 家礼物商店，如果在第 $i$ 个商店中为朋友 $j$ 买礼物，朋友 $j$ 将获得 $p_{ij}$ 的快乐值。

由于时间紧迫， Vlad 最多只会在 $n-1$ 家不同的商店中买礼物。请你使每位朋友能获得的快乐值中的最小值最大。

输入格式

第一行一个整数 $t$，表示有 $t$ 组测试数据。

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

保证 $t\le 10^4$，$p_{ij}\le 10^9$，$n\ge 2$，且所有测试数据中 $n\cdot m$ 的和不超过 $10^5$。

输出格式

输出 $t$ 行，每行包含对应测试数据的答案，即 Vlad 的朋友中最小快乐值的最大值。

样例 #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

---

裸二分，又不会判定，我代码水平就是shit

1. 某个商店至少负责两个商品
2. 每个人只能买一件物品！
3. 每个人都要有物品

二分答案裸题。

#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

题面翻译

题目描述

哆来咪·苏伊特参加了 $n$ 场比赛。 比赛 $i$ 只能在第 $i$ 天进行。比赛 $i$ 的难度为 $a_i$。最初，哆来咪的 IQ 为 $q$ 。 在第 $i$ 天，哆来咪将选择是否参加比赛 i。只有当她当前的 IQ 大于 $0$ 时，她才能参加比赛。

如果哆来咪选择在第 $i$ 天参加比赛 $i$，则会发生以下情况：

• 如果 $a_i>q$，哆来咪会觉得自己不够聪明，所以 $q$ 将会减 $1$；
• 否则，什么都不会改变。

如果她选择不参加比赛，一切都不会改变。哆来咪想参加尽可能多的比赛。请给哆来咪一个解决方案。

输入格式

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

第二行包含两个整数 $n$ 和 $q$ ($1\le n\le 10^5$, $1\le q\le 10^9$)，表示比赛次数和哆来咪最开始时的 IQ。

第三行包含 $n$ 个整数 $a_1,a_2\cdots a_n$($1\le a_i\le 10^9$)，表示每场比赛的难度。

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

输出格式

对于每组数据，输出一个二进制字符串 $s$，如果哆来咪应该选择参加比赛 $i$，则 $s_i=1$，否则 $s_i=0$。 字符串中 $1$ 的数量应该尽可能的多，并且当她的 IQ 为 $0$ 或更低时，她不应该参加比赛。

如果有多个解决方案，你可以输出任意一个。

样例说明

在第一个测试用例中，哆来咪参加了唯一的比赛。她的 IQ 没有下降。

在第二个测试用例中，哆来咪参加了两个比赛。在参加比赛 $2$ 后，她的 IQ 下降了 $1$。

在第三个测试用例中，哆来咪参加了比赛 $1$ 和比赛 $2$。她的 IQ 在参加比赛 $2$ 后降至 $0$，因此她无法参加比赛 $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

---

智商不足警告，真看不懂题解咋倒着考虑的。两端性不会分析。
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;
}