Блог пользователя MS1908

Number of special tuples
Автор MS1908, история, 5 лет назад, По-английски

I'm trying to solve the following problem from Hanoi Olympiad in Informatics.

Problem: Given arrays $$$A$$$ $$$a_1,a_2,\ldots, a_m$$$ and $$$B$$$ $$$b_1,b_2,\ldots, b_n$$$. From $$$A$$$ we take $$$a_j, a_k$$$ and from $$$B$$$ we take $$$b_i$$$ such that the tuple formed by these numbers satisfies $$$a_j < b_i < a_k$$$ or $$$a_k < b_i < a_j$$$. Such triple is called special. These numbers will be remove from the original arrays, and we repeat the process with the remaining numbers of the arrays. Find the maximum number of special triples.

Input: First line contains $$$m, n$$$ ($$$2\le m\le 10^5, 2\le n\le 10^5$$$). The second line contains $$$a_1,a_2,\ldots, a_m$$$ ($$$1\le a_i\le 10^9$$$) and the third line contains $$$b_1,b_2,\ldots, b_n$$$ ($$$1\le b_i\le 10^9$$$).

Output: Maximum number of special triples.

**Example: **

Input:

5 3

5 1 3 2 2

2 4 3

Output:

2

Explanation: We can choose $$$a_1=5$$$, $$$a_4=2$$$, $$$b_2=4$$$ and $$$a_2=1$$$, $$$a_3=3$$$, $$$b_1=2$$$.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

I suggest greedy solution like this:

make two multisets a and b and push elements into them. Then lets do something like this:

auto z = a.begin();
auto x = b.upper_bound(*z);
a.erase(z);
z = a.upper_bound(*x);
b.erase(x);
a.erase(z);
ans ++;

repeat this while a.size()>=2 and b.size()>=1

Also you need to check if any of the iterators is equal to end

→ Ответить