Atcoder解いてみた AtCoder Beginner Contest C - Invisible Hand

AtCoder Beginner Contest C - Invisible Hand

問題はこちら

回答

解の候補が有効か無効かどうかの単調性に着目して、解の二分探索を行う

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>
#include <iomanip>
#include <random>


int N, M;
std::vector<long long> A;
std::vector<long long> B;

bool Judge(long long val){
	// 売っていい人の数
	int sellNum = std::upper_bound(A.begin(), A.end(), val) - A.begin();

	// 買っていい人の数
	int buyNum = B.end() - std::lower_bound(B.begin(), B.end(), val);

	return sellNum >= buyNum;
}

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N >> M;

	A.resize(N);
	B.resize(M);


	for (int i = 0; i < N; i++) {
		std::cin >> A[i];
	}

	for (int i = 0; i < M; i++) {
		std::cin >> B[i];
	}
	
	std::sort(A.begin(), A.end());
	std::sort(B.begin(), B.end());

	const long long INF = 1e18;
	long long ac = INF;
	long long wa = 0;

	while(wa + 1<ac){
		long long X = (wa + ac) / 2;

		if (Judge(X)) {
			ac = X;
		}
		else {
			wa = X;
		}
	}
	
	std::cout << ac << std::endl;

	return 0;
}