Link: E. The Contest

E. The Contest

Description:
A team of three programmers is going to play a contest. The contest consists of n problems, numbered from 1 to n. Each problem is printed on a separate sheet of paper. The participants have decided to divide the problem statements into three parts: the first programmer took some prefix of the statements (some number of first paper sheets), the third contestant took some suffix of the statements (some number of last paper sheets), and the second contestant took all remaining problems. But something went wrong — the statements were printed in the wrong order, so the contestants have received the problems in some random order.

The first contestant has received problems a1,1,a1,2,…,a1,k1. The second one has received problems a2,1,a2,2,…,a2,k2. The third one has received all remaining problems (a3,1,a3,2,…,a3,k3).

The contestants don't want to play the contest before they redistribute the statements. They want to redistribute them so that the first contestant receives some prefix of the problemset, the third contestant receives some suffix of the problemset, and the second contestant receives all the remaining problems.

During one move, some contestant may give one of their problems to other contestant. What is the minimum number of moves required to redistribute the problems?

It is possible that after redistribution some participant (or even two of them) will not have any problems.

Input
The first line contains three integers k1,k2 and k3 (1≤k1,k2,k3≤2e5,k1+k2+k3≤2e5) — the number of problems initially taken by the first, the second and the third participant, respectively.

The second line contains k1 integers a1,1,a1,2,…,a1,k1 — the problems initially taken by the first participant.

The third line contains k2 integers a2,1,a2,2,…,a2,k2 — the problems initially taken by the second participant.

The fourth line contains k3 integers a3,1,a3,2,…,a3,k3 — the problems initially taken by the third participant.

It is guaranteed that no problem has been taken by two (or three) participants, and each integer ai,j meets the condition 1≤ai,j≤n, where n=k1+k2+k3.

Output
Print one integer — the minimum number of moves required to redistribute the problems so that the first participant gets the prefix of the problemset, the third participant gets the suffix of the problemset, and the second participant gets all of the remaining problems.

Examples
input
2 1 2
3 1
4
2 5
output
1
input
3 2 1
3 2 1
5 4
6
output
0
input
2 1 3
5 6
4
1 2 3
output
3
input
1 5 1
6
5 1 2 4 7
3
output
2
Note
In the first example the third contestant should give the problem 2 to the first contestant, so the first contestant has 3 first problems, the third contestant has 1 last problem, and the second contestant has 1 remaining problem.

In the second example the distribution of problems is already valid: the first contestant has 3 first problems, the third contestant has 1 last problem, and the second contestant has 2 remaining problems.

The best course of action in the third example is to give all problems to the third contestant.

The best course of action in the fourth example is to give all problems to the second contestant.

Problem solving:
这道题的意思就是三个人一队做n道题，第一个人只做前面几个题，第三个人只做后面几个题，剩下的题第二个人做。但是现在发题的人给他们发的顺序并不是他们想要的顺序，问你最少需要换多少次可以同时满足三个人的要求。（可以出现某几个人一道题没有的情况）

一开始毫无思路，但是仔细一想，按照题目描述的来就是三个人做题的序号就是一个严格的升序。所以我们可以把三个人的题自己排序完之后全部放在一起，求一个最大上升子序列。然后用总题数减最大上升子序列的长度就是答案。这个应该还是很好理解的。

Code:

#include <iostream>
#include <vector>
#include <algorithm>
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int       a[maxn], b[maxn], c[maxn], d[maxn], dp[maxn];
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    int x, y, z;
    cin >> x >> y >> z;
    for (int i = 0; i < x; i++)
        cin >> a[i];
    for (int i = 0; i < y; i++)
        cin >> b[i];
    for (int i = 0; i < z; i++)
        cin >> c[i];
    sort(a, a + x);
    sort(b, b + y);
    sort(c, c + z);
    for (int i = 0; i < x; i++)
    {
        d[i] = a[i];
    }
    for (int i = x; i < x + y; i++)
    {
        d[i] = b[i - x];
    }
    for (int i = x + y; i < x + y + z; i++)
        d[i] = c[i - x - y];
    cout << endl;
    fill(dp, dp + x + y + z, inf);
    for (int i = 0; i < x + y + z; i++)
    {
        *lower_bound(dp, dp + x + y + z, d[i]) = d[i];
    }
    cout << x + y + z - (lower_bound(dp, dp + x + y + z, inf) - dp) << endl;
    return 0;
}
赏