[USACO21JAN] Even More Odd Photos B

Luogu

IDLGP9941

Time1000ms

Memory256MB

DifficultyP2

数学贪心USACO2021O2优化

Farmer John 正再一次尝试给他的 $N$ 头奶牛拍照（$2\le N\le 1000$）。每头奶牛有一个范围在 $1\ldots 100$ 之内的整数的「品种编号」。Farmer John 对他的照片有一个十分古怪的构思：他希望将所有的奶牛分为不相交的若干组（换句话说，将每头奶牛分到恰好一组中）并将这些组排成一行，使得第一组的奶牛的品种编号之和为偶数，第二组的编号之和为奇数，以此类推，奇偶交替。 Farmer John 可以分成的最大组数是多少？ ## Input 输入的第一行包含 $N$。下一行包含 $N$ 个空格分隔的整数，为 $N$ 头奶牛的品种编号。 ## Output 输出 Farmer John 的照片中的最大组数。可以证明，至少存在一种符合要求的分组方案。 [samples] ## Note ### 样例解释 1 在这个样例中，以下是一种分成最大组数三组的方案。将 1 和 3 分在第一组，5、7 和 9 分在第二组，11 和 13 分在第三组。 ### 样例解释 2 在这个样例中，以下是一种分成最大组数五组的方案。将 2 分在第一组，11 分在第二组，13 和 1 分在第三组，15 分在第四组，17 和 3 分在第五组。

Samples

Input #1

7
1 3 5 7 9 11 13

Output #1

Input #2

7
11 2 17 13 1 15 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[USACO21JAN] Even More Odd Photos B",
    "description": {
      "content": "Farmer John 正再一次尝试给他的 $N$ 头奶牛拍照（$2\\le N\\le 1000$）。 每头奶牛有一个范围在 $1\\ldots 100$ 之内的整数的「品种编号」。Farmer John 对他的照片有一个十分古怪的构思：他希望将所有的奶牛分为不相交的若干组（换句话说，将每头奶牛分到恰好一组中）并将这些组排成一行，使得第一组的奶牛的品种编号之和为偶数，第二组的编号之和为奇数，以此类推",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9941"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Farmer John 正再一次尝试给他的 $N$ 头奶牛拍照（$2\\le N\\le 1000$）。\n\n每头奶牛有一个范围在 $1\\ldots 100$ 之内的整数的「品种编号」。Farmer John 对他的照片有一个十分古怪的构思：他希望将所有的奶牛分为不相交的若干组（换句话说，将每头奶牛分到恰好一组中）并将这些组排成一行，使得第一组的奶牛的品种编号之和为偶数，第二组的编号之和为奇数，以此类推...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments