[COCI 2012/2013 #2] LANCI

Luogu

IDLGP8297

Time1000ms

Memory32MB

DifficultyP4

贪心2012COCI（克罗地亚）

Mirko 在阁楼里发现了 $N$ 个链。每个链由一些节组成，其中每个节最多有两个相邻节。每个节都可以打开或合上，因此可以将链分开或连成更长的链。 Mirko 希望把所有链连成一条巨大的链，并且打开或合上尽可能少的节。例如，假设 Mirko 只有 $3$ 个链，每个链只有一个节，他可以打开其中一个，并且连上另外两个再合上。 ![](https://cdn.luogu.com.cn/upload/image_hosting/he62ksg3.png) 给定链的数量以及每个链的长度，找到 Mirko 必须打开和关闭的最小节数，使它们全部在一个长链上。 ## Input 第一行一个整数 $N\ (2\le N\le 5\times 10^5)$，表示链的数量。第二行 $N$ 个正整数 $L_i\ (1\le L_i\le 10^6)$，表示第 $i$ 个链的长度。 ## Output 输出仅一行一个整数，表示最少要打开的节数。 [samples] ## Background **本题分值按 COCI 原题设置，满分 $100$。**

Samples

Input #1

2
3 3

Output #1

Input #2

3
1 1 1

Output #2

Input #3

5
4 3 5 7 9

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2012/2013 #2] LANCI",
    "description": {
      "content": "Mirko 在阁楼里发现了 $N$ 个链。每个链由一些节组成，其中每个节最多有两个相邻节。每个节都可以打开或合上，因此可以将链分开或连成更长的链。 Mirko 希望把所有链连成一条巨大的链，并且打开或合上尽可能少的节。 例如，假设 Mirko 只有 $3$ 个链，每个链只有一个节，他可以打开其中一个，并且连上另外两个再合上。 ![](https://cdn.luogu.com.cn/uplo",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 32768
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8297"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mirko 在阁楼里发现了 $N$ 个链。每个链由一些节组成，其中每个节最多有两个相邻节。每个节都可以打开或合上，因此可以将链分开或连成更长的链。\n\nMirko 希望把所有链连成一条巨大的链，并且打开或合上尽可能少的节。\n\n例如，假设 Mirko 只有 $3$ 个链，每个链只有一个节，他可以打开其中一个，并且连上另外两个再合上。\n\n![](https://cdn.luogu.com.cn/uplo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments