[语言月赛 202409] 考试

Luogu
IDLGB4033
Time1000ms
Memory512MB
DifficultyP3
贪心2024O2优化语言月赛
迅风和他的好朋友一同参加了 $n$ 场考试,而迅风拥有预知未来和**提升自己分数**的能力。 在第 $i$ 场考试中,迅风知道他自己原来取得 $a_i$ 分,他的好朋友**一定会**取得 $b_i$ 分。 而他们很喜欢争个高下,设迅风在 $x$ 场考试中分数比他的好朋友高,在 $y$ 场考试中分数比他的好朋友低,那么: - 若 $x>y$,则说明在这 $n$ 场考试中,迅风更胜一筹。 - 若 $x<y$,则说明迅风的好朋友更胜一筹。 - 若 $x=y$,则说明两人打平。 迅风发现自己可能会输给他的朋友,于是他可以选择若干场考试**提升自己的分数**,记增加的分数总和为 $sum$。 迅风想知道,自己要在这 $n$ 场考试中更胜一筹,所需的 $sum$ 最小为多少? ## Input 输入的第一行有一个正整数 $n$ 表示考试数量。 第二行有 $n$ 个正整数 $a_1,\ldots,a_n$,表示迅风每场考试的分数。 第三行有 $n$ 个正整数 $b_1,\ldots, b_n$,表示迅风的朋友每场考试的分数。 ## Output 输出一个非负整数 $sum$ 表示答案。 [samples] ## Note **【样例 1 解释】** 只要把第 $3$ 次考试的得分提升 $6$ 分,就可以在第 $2,3$ 次考试中获得比朋友更高的分数,从而 $x=2,y=1$,迅风更胜一筹。 **【样例 2 解释】** 只要把第 $1,3,4$ 次考试的得分各提升 $1$ 分,就可以让 $x=2,y=1$,从而让迅风更胜一筹。 **【样例 3 解释】** 哪怕不提升分数,也有 $x=2,y=0$ 了,迅风已经更胜一筹。 **【数据范围】** 本题共有 $20$ 个测试点,测试点等分。 |测试点编号|$n\le$|特殊性质| |:-:|:-:|:-:| |$1\sim 2$|$2$|| |$3\sim 6$|$100$|$a_i,b_i\le 2$| |$7$|$1000$|每次考试两人成绩都相等| |$8\sim 11$|$1000$|迅风成绩递增,他朋友成绩递减| |$12\sim 15$|$1000$|每次考试两人成绩都不相等| |$16\sim 20$|$1000$|| **关于测试点 $8\sim 11$,这里的递增和递减是不严格的,如 $1,5,5,8,10$ 也视为递增。** 特别地,编号为奇数的测试点 $n$ 为奇数,编号为偶数的测试点 $n$ 为偶数。 对于全体数据,保证 $1\le n\le 1000$,$1\le a_i,b_i\le 10^4$(也就是 $10000$),输入皆为整数。 **【后记】** 祝各位参加 $2024$ 年 CSP 比赛的选手 rp++!
Samples
Input #1
3
30 10 9995
100 1 10000
Output #1
6
Input #2
4
10 20 50 90
11 22 50 90
Output #2
3
Input #3
3
100 100 1
3 3 1
Output #3
0
API Response (JSON)
{
  "problem": {
    "name": "[语言月赛 202409] 考试",
    "description": {
      "content": "迅风和他的好朋友一同参加了 $n$ 场考试,而迅风拥有预知未来和**提升自己分数**的能力。 在第 $i$ 场考试中,迅风知道他自己原来取得 $a_i$ 分,他的好朋友**一定会**取得 $b_i$ 分。 而他们很喜欢争个高下,设迅风在 $x$ 场考试中分数比他的好朋友高,在 $y$ 场考试中分数比他的好朋友低,那么: - 若 $x>y$,则说明在这 $n$ 场考试中,迅风更胜一筹。 - 若",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4033"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "迅风和他的好朋友一同参加了 $n$ 场考试,而迅风拥有预知未来和**提升自己分数**的能力。\n\n在第 $i$ 场考试中,迅风知道他自己原来取得 $a_i$ 分,他的好朋友**一定会**取得 $b_i$ 分。\n\n而他们很喜欢争个高下,设迅风在 $x$ 场考试中分数比他的好朋友高,在 $y$ 场考试中分数比他的好朋友低,那么:\n\n- 若 $x>y$,则说明在这 $n$ 场考试中,迅风更胜一筹。\n- 若...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments