Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 21685. 【NOIP Round #2】保序回归问题

统计

题目描述

本题中,你需要解决一个著名的 NP 问题——保序回归问题。

保序回归问题要有变量:你需要给出一个长度为 $n$ 的整数序列 $(x_1,x_2,\ldots,x_n)$,满足下文中的所有条件。

保序回归问题要有约束:一般的保序回归问题需要保持偏序,但这样就成板子题了,所以在本题中你只需要保证 $\prod_{i=1}^n x_i>0$。

保序回归问题要有目标函数:也就是回归代价,和其它 $L_1$ 保序回归问题一样,在给出 $n$ 个目标参数 $y_1,y_2,\ldots,y_n$ 的前提下,你需要最小化 $\sum_{i=1}^n |x_i-y_i|$。

保序回归问题不一定要有多组询问,本题也没有,但是每个测试点包含有多组测试数据。

输入格式

第一行包括一个整数 $T$,代表测试数据组数。

接下来依次读入 $T$ 组测试数据,对于每组测试数据:

  • 第一行包括一个整数 $n$。
  • 第二行包括 $n$ 个用空格分隔开的整数,依次为 $y_1,y_2,\ldots y_n$。

输出格式

共 $T$ 行,每行一个整数,依次代表每组测试数据的答案。

样例

样例输入 1

3
3
-3 -2 -2
9
9 9 8 2 4 4 3 5 3
3
0 0 0

样例输出 1

3
0
3

样例解释 1

对于第一组测试数据,一种满足条件的 $(x_1,x_2,x_3)$ 为 $(-3,1,-2)$。其满足 $\prod_{i=1}^n x_i=(-3)\times 1\times (-2)=6>0$,其回归代价为 $\sum_{i=1}^n|x_i-y_i|=|(-3)-(-3)|+|1-(-2)|+|(-2)-(-2)|=3$。可以证明没有回归代价 $<3$ 的合法序列,故答案为 $3$。

对于第三组测试数据,一种满足条件的序列为 $(1,-1,-1)$。

样例输入 / 输出 2

见下发文件中的 ex_isoreg2.in/ex_isoreg2.ans

数据范围

本题共有 $10$ 个测试点,每个测试点 $10$ 分。

记 $\sum n$ 为某个测试点中所有测试数据的 $n$ 之和。

对于所有测试点,保证 $1\le T,n,\sum n\le 2\times10^5,-10^9\le y_i\le 10^9$。

对于测试点 $1$,保证 $T,n,|y_i|\le 5$。

对于测试点 $2,3$,保证 $\sum n,|y_i|\le 100$。

对于测试点 $4,5$,保证 $\sum n,|y_i|\le 1000$。

对于测试点 $6$,保证对于每组测试数据,$\prod_{i=1}^n y_i\ne 0$。

对于测试点 $7$,保证对于每组测试数据,$\prod_{i=1}^n y_i=0$。

对于测试点 $8,9,10$,无特殊限制。