[NFLSPC #6] 等差数列

Luogu
IDLGP9936
Time1000ms
Memory1024MB
DifficultyP4
三分O2优化
*Alek 岁*在某知名 OJ *代码力量*上做了 $a_i$ 道难度为 $i$ 的题。他希望做一些题使得 $a_i$ 形成 **公差非正** 的等差数列,这样画出来的统计图表很好看。 尽管 *Alek 岁*一天能做 42 道题,但他依然希望做尽可能少的题达到目标。你需要求出新做题数的最小值。 你可以认为 OJ 上有足够多的各种难度的题目。 ## Input 第一行一个整数 $T$ 表示数据组数。 对于每组数据: - 第一行一个整数 $n$ 表示难度总数。 - 第二行 $n$ 个整数 $a_i$。 ## Output 对于每组数据,输出一行一个整数表示答案。 [samples] ## Background ![](https://cdn.luogu.com.cn/upload/image_hosting/asxexdko.png) ![](https://cdn.luogu.com.cn/upload/image_hosting/rzayzc9p.png) ## Note 对于所有数据,$1\leq T\leq 100$,$1\leq n, \sum n\leq 10 ^ 5$,$1\leq a_i\leq 10 ^ 9$。 - 子任务 1($30$ 分):$\sum n \leq 10 ^ 3$。 - 子任务 2($70$ 分):无特殊限制。 Source:NFLSPC #6 L by Alex_Wei
Samples
Input #1
6
2
822 1064
2
1064 822
4
1 3 4 2
4
2 4 3 1
6
2 6 2 1 4 4
9
9 9 8 2 4 4 3 5 3
Output #1
242
0
6
4
17
25
API Response (JSON)
{
  "problem": {
    "name": "[NFLSPC #6] 等差数列",
    "description": {
      "content": "*Alek 岁*在某知名 OJ *代码力量*上做了 $a_i$ 道难度为 $i$ 的题。他希望做一些题使得 $a_i$ 形成 **公差非正** 的等差数列,这样画出来的统计图表很好看。 尽管 *Alek 岁*一天能做 42 道题,但他依然希望做尽可能少的题达到目标。你需要求出新做题数的最小值。 你可以认为 OJ 上有足够多的各种难度的题目。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9936"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "*Alek 岁*在某知名 OJ *代码力量*上做了 $a_i$ 道难度为 $i$ 的题。他希望做一些题使得 $a_i$ 形成 **公差非正** 的等差数列,这样画出来的统计图表很好看。\n\n尽管 *Alek 岁*一天能做 42 道题,但他依然希望做尽可能少的题达到目标。你需要求出新做题数的最小值。\n\n你可以认为 OJ 上有足够多的各种难度的题目。\n\n## Input\n\n第一行一个整数 $T$ 表示数...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments