#P3180. [Coci2012]ograda

    ID: 2356 传统题 1000ms 512MiB 尝试: 97 已通过: 29 难度: 6 上传者: 标签>难度分类普及+/提高-贪心排序贪心排序与序列处理自定义排序规则交换论证构造与建模排列构造CF1900

[Coci2012]ograda

[COCI 2011/2012 #4] OGRADA

题目描述

Mirko 村里的围栏都由 NN 块高度各不相同的木板排成。围栏的美观度是每对相邻木板的高度差的绝对值之和。

Mirko 买了 NN 块木板,想把围栏排得和 Slavko 的围栏相似,同时使美观度尽可能大。若两道围栏每对相邻木板的升降关系相同,就称它们相似。也就是说,对每个 1≤i<N1\le i<N,若 Slavko 围栏的第 ii 块木板低于第 i+1i+1 块,Mirko 的围栏也要在此处上升。若 Slavko 的围栏在此处下降,Mirko 的围栏也要下降。

给出 Slavko 围栏从左到右的木板高度 AiA_i,以及 Mirko 买来的木板高度 BiB_i。求 Mirko 围栏的最大美观度以及一种达到这个值的相似排列。

输入格式

第一行包含整数 NN(2≤N≤3×1052\le N\le 3\times 10^5)。

第二行包含 NN 个互不相同的正整数 AiA_i。

第三行包含 NN 个互不相同的正整数 BiB_i。

保证每个高度都小于 10910^9。

输出格式

第一行输出最大美观度。

第二行输出 NN 个整数,表示 Mirko 的木板从左到右的排列。如有多种最优排列,可以输出任意一种。

4
5 7 4 9
1 2 3 4
7
2 4 1 3
10
9 5 1 2 6 7 4 18 20 12
10 40 20 30 50 70 80 100 1000 500
3010
100 80 10 40 50 1000 20 70 500 30

样例 1 解释

木板排列 美观度
1,3,2,41,3,2,4 2+1+2=52+1+2=5
1,4,2,31,4,2,3 3+2+1=63+2+1=6
2,3,1,42,3,1,4 1+2+3=61+2+3=6
2,4,1,32,4,1,3 2+3+2=72+3+2=7
3,4,1,23,4,1,2 1+3+1=51+3+1=5

原题评分

在原比赛中,若第一行的美观度正确而第二行缺失或错误,可获该测试用例分值的 50%50\%。

原题面 PDF