// https://atcoder.jp/contests/abc460/tasks/abc460_c /* * What is given? * N = number of pieces of shari * M = number of pieces of neta * * Each shari an neta can have different weights. The weights for each * shari and neta are given as an array. * * [ a1 a2 a3 ... ai ] = weights of the i-th shari * [ b1 b2 b3 ... bj ] = weights of the j-th neta * * What to do? * Combine values in the arrays above in a way that maximum pairs are * possible. Each pair will have an unique item from ai and bj each. A * valid pair will have the value (2 * ai) >= bj. */ /* * [ 4 2 1 8 ] => (double) => [ 8 4 2 16 ] => (sort) => [ 2 4 8 16 ] * [ 14 9 3 2 9 ] => (sort) => [ 2 3 9 9 14 ] * * (shari, neta) * correct pairs: (8 3) (4 2) (16 14) * attempted pairs: (2 2) (4 3) (16 9) * * I iterate through the doubled and sorted array of sharis, and try to * match the neta to it with the minimum valid weight of neta required * for it. This greedy approach also gave us the correct answer. * * [3 5] => [6 10] => [6 10] * [5 6] => [5 6] * * (6 5) (10 6) * * (10 5) (6 6) * * [2, 3, 8] => [4 6 16] => [4 6 16] * [3, 4, 15] => [3 4 15] * * sorted + smallest (4 3) (6 4) (16 15) * sorted + largest (4 4) (6 3) (16 3) * * [1 2 3] => [2 4 6] => [2 4 6] * [2 2 5] => [2 2 5] * * sorted + smallest (1 2) (2 2) (3 5) * sorted + largest (1 2) (2 2) (3 5) * * both sorted, then largest-to-largest-frist is the correct approach. */ #include #include #include typedef signed char i8; typedef signed short i16; typedef signed long i32; typedef signed long long i64; typedef unsigned char u8; typedef unsigned short u16; typedef unsigned long u32; typedef unsigned long long u64; static inline u32 solve( const u32 N, std::vector s, const u32 M, std::vector n) { u32 pairs = 0; std::ranges::sort(s, std::greater<>{}); std::ranges::sort(n, std::greater<>{}); u32 i = 0, j = 0; while (i < N && j < M) { if (2 * s[i] >= n[j]) { ++pairs; ++i; ++j; } else { ++j; } } return pairs; } int main(void) { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); u32 N, M; std::cin >> N >> M; std::vector sharis(N); std::vector netas(M); for (u32 i = 0; i < N; ++i) std::cin >> sharis[i]; for (u32 i = 0; i < M; ++i) std::cin >> netas[i]; std::cout << solve(N, std::move(sharis), M, std::move(netas)); }