CF1257E.The Contest

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:512MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

A team of three programmers is going to play a contest. The contest consists of nn problems, numbered from 11 to nn. 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,k1a_{1, 1}, a_{1, 2}, \dots, a_{1, k_1}. The second one has received problems a2,1,a2,2,…,a2,k2a_{2, 1}, a_{2, 2}, \dots, a_{2, k_2}. The third one has received all remaining problems (a3,1,a3,2,…,a3,k3a_{3, 1}, a_{3, 2}, \dots, a_{3, k_3}).

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.

一支由三名程序员组成的队伍即将参加一场竞赛。该竞赛共有 nn 道题目,编号从 11 到 nn。每道题目的题面都印在一张独立的纸上。参赛者们原计划将题面分成三部分:第一名程序员取题面的一个前缀(即最前面若干张纸),第三名程序员取题面的一个后缀(即最后若干张纸),第二名程序员则取其余所有题目。但出了点差错——题面被错误地打乱了顺序,因此三名参赛者收到的题目是某种随机顺序。

第一名程序员收到了题目 a1,1,a1,2,…,a1,k1a_{1, 1}, a_{1, 2}, \dots, a_{1, k_1};
第二名程序员收到了题目 a2,1,a2,2,…,a2,k2a_{2, 1}, a_{2, 2}, \dots, a_{2, k_2};
第三名程序员收到了剩余的所有题目(即 a3,1,a3,2,…,a3,k3a_{3, 1}, a_{3, 2}, \dots, a_{3, k_3})。

在正式开始比赛前,参赛者们希望重新分配题面,使得:第一名程序员获得题集的一个前缀,第三名程序员获得题集的一个后缀,第二名程序员获得中间剩余的所有题目。

每次操作中,某位参赛者可将自己手中的一道题目交给另一位参赛者。问:完成上述重新分配所需的最少操作次数是多少?

注意:重新分配后,有可能某位(甚至两位)参赛者手中不再持有任何题目。

输入格式

The first line contains three integers k1,k2k_1, k_2 and k3k_3 (1≤k1,k2,k3≤2⋅105,k1+k2+k3≤2⋅1051 \le k_1, k_2, k_3 \le 2 \cdot 10^5, k_1 + k_2 + k_3 \le 2 \cdot 10^5) — the number of problems initially taken by the first, the second and the third participant, respectively.

The second line contains k1k_1 integers a1,1,a1,2,…,a1,k1a_{1, 1}, a_{1, 2}, \dots, a_{1, k_1} — the problems initially taken by the first participant.

The third line contains k2k_2 integers a2,1,a2,2,…,a2,k2a_{2, 1}, a_{2, 2}, \dots, a_{2, k_2} — the problems initially taken by the second participant.

The fourth line contains k3k_3 integers a3,1,a3,2,…,a3,k3a_{3, 1}, a_{3, 2}, \dots, a_{3, k_3} — 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,ja_{i, j} meets the condition 1≤ai,j≤n1 \le a_{i, j} \le n, where n=k1+k2+k3n = k_1 + k_2 + k_3.

第一行包含三个整数 k1,k2k_1, k_2 和 k3k_3(1≤k1,k2,k3≤2⋅1051 \le k_1, k_2, k_3 \le 2 \cdot 10^5,且 k1+k2+k3≤2⋅105k_1 + k_2 + k_3 \le 2 \cdot 10^5),分别表示第一、第二和第三位参与者最初选取的问题数量。

第二行包含 k1k_1 个整数 a1,1,a1,2,…,a1,k1a_{1, 1}, a_{1, 2}, \dots, a_{1, k_1},表示第一位参与者最初选取的问题编号。

第三行包含 k2k_2 个整数 a2,1,a2,2,…,a2,k2a_{2, 1}, a_{2, 2}, \dots, a_{2, k_2},表示第二位参与者最初选取的问题编号。

第四行包含 k3k_3 个整数 a3,1,a3,2,…,a3,k3a_{3, 1}, a_{3, 2}, \dots, a_{3, k_3},表示第三位参与者最初选取的问题编号。

保证任意一个问题不会被两位(或三位)参与者同时选取,且每个整数 ai,ja_{i, j} 均满足条件 1≤ai,j≤n1 \le a_{i, j} \le n,其中 n=k1+k2+k3n = k_1 + k_2 + k_3。

输出格式

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.

输出一个整数——重新分配题目所需的最少操作次数,使得第一位参与者获得题目的前缀,第三位参与者获得题目的后缀,第二位参与者获得剩余的所有题目。

输入输出样例

  • 输入#1

    2 1 2
    3 1
    4
    2 5

    输出#1

    1
  • 输入#2

    3 2 1
    3 2 1
    5 4
    6

    输出#2

    0
  • 输入#3

    2 1 3
    5 6
    4
    1 2 3

    输出#3

    3
  • 输入#4

    1 5 1
    6
    5 1 2 4 7
    3

    输出#4

    2

说明/提示

In the first example the third contestant should give the problem 22 to the first contestant, so the first contestant has 33 first problems, the third contestant has 11 last problem, and the second contestant has 11 remaining problem.

In the second example the distribution of problems is already valid: the first contestant has 33 first problems, the third contestant has 11 last problem, and the second contestant has 22 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.

在第一个例子中,第三位参赛者应将第 22 题交给第一位参赛者,从而使第一位参赛者拥有 33 道“前面的题”,第三位参赛者拥有 11 道“后面的题”,第二位参赛者拥有 11 道“剩余的题”。

在第二个例子中,题目分配已满足要求:第一位参赛者拥有 33 道“前面的题”,第三位参赛者拥有 11 道“后面的题”,第二位参赛者拥有 22 道“剩余的题”。

在第三个例子中,最优策略是将所有题目都分配给第三位参赛者。

在第四个例子中,最优策略是将所有题目都分配给第二位参赛者。

输入解题思路,AI测评打分。不知道怎么写?

首页