当前位置：首页 > news >正文

打卡信奥刷题（3066）用C++实现信奥题 P6877 [JOI 2020 Final] 只不过是长的领带 / Just Long Neckties

news 2026/6/25 21:39:49

P6877 [JOI 2020 Final] 只不过是长的领带 / Just Long Neckties

题目描述

JOI 公司发明了一种领带，一共有N + 1 N+1N+1条领带，编号为1 11到N + 1 N+1N+1，第i ii条领带的长度为A i A_iAi。

JOI 公司开了一个派对，派对中有N NN名员工，第j jj名员工刚开始戴了长度为B j B_jBj的领带。

派对这样举行：

首先，JOI 公司的老板 JOI 君选出一条领带拿走。
然后，每个员工选一条领带，保证没有两名员工选了相同的领带。
最后，他们取下最先戴的领带，戴上选择的领带。

如果一名员工刚开始戴的领带长度为b bb，选择的领带长度为a aa，那么他就会产生max ⁡ { a − b , 0 } \max\{a-b,0\}max{a−b,0}的奇怪感，整场派对的奇怪程度为所有员工的奇怪感的最大值。

于是 JOI 君定义C k C_kCk为他选出第k kk条领带后的最小奇怪程度。

JOI 君想知道C k C_kCk的具体值。

输入格式

第一行一个整数N NN代表员工数。
第二行N + 1 N+1N+1个整数A i A_iAi代表每个领带的长度。
第三行N NN个整数B j B_jBj代表每个人最开始戴的领带的长度。

输出格式

一行N + 1 N+1N+1个整数C k C_kCk代表选出每个领带后的最小奇怪程度。

输入输出样例 #1

输入 #1

3 4 3 7 6 2 6 4

输出 #1

2 2 1 1

输入输出样例 #2

输入 #2

5 4 7 9 10 11 12 3 5 7 9 11

输出 #2

4 4 3 2 2 2

说明/提示

样例 1 解释

让我们假设 JOI 君选择了第4 44条领带，那么员工们可以这么选择：

第1 11名员工选择第1 11条领带，产生奇怪感2 22
第2 22名员工选择第2 22条领带，产生奇怪感0 00
第3 33名员工选择第3 33条领带，产生奇怪感3 33

奇怪程度为3 33。

但我们还可以继续减小奇怪程度：

第1 11名员工选择第2 22条领带，产生奇怪感1 11
第2 22名员工选择第3 33条领带，产生奇怪感1 11
第3 33名员工选择第1 11条领带，产生奇怪感0 00

奇怪程度为1 11。

因此C 4 = 1 C_4=1C4=1。

数据规模与约定

本题采用捆绑测试。

Subtask 1（1 pts）：N ≤ 10 N \le 10N≤10。
Subtask 2（8 pts）：N ≤ 2000 N \le 2000N≤2000。
Subtask 3（91 pts）：无特殊限制。

对于100 % 100\%100%的数据：

1 ≤ N ≤ 2 × 10 5 1 \le N \le 2 \times 10^51≤N≤2×105。
1 ≤ A i ≤ 10 9 1 \le A_i \le 10^91≤Ai≤109。
1 ≤ B j ≤ 10 9 1 \le B_j \le 10^91≤Bj≤109。

说明

翻译自第19回日本情報オリンピック本選 A 長いだけのネクタイ。

C++实现

#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=2e5+5;structMonkey{intval,id;}a[N];boolcmp(Monkey p,Monkey q){returnp.val<q.val;}intb[N],pre[N],suf[N],ans[N];//pre[i]记录ai-bi前缀mx，suf[i]记录ai+1 - bi后缀mxintmain(){ios::sync_with_stdio(false);intn;scanf("%d",&n);for(inti=1;i<=n+1;i++)scanf("%d",&a[i].val),a[i].id=i;for(inti=1;i<=n;i++)scanf("%d",&b[i]);sort(a+1,a+n+2,cmp),sort(b+1,b+n+1);for(inti=1;i<=n;i++)pre[i]=max(pre[i-1],a[i].val-b[i]);for(inti=n;i;i--)suf[i]=max(suf[i+1],a[i+1].val-b[i]);for(inti=1;i<=n+1;i++)ans[a[i].id]=max(pre[i-1],suf[i]);for(inti=1;i<=n+1;i++)printf("%d ",max(ans[i],0));return0;}