[USACO22DEC] Cow College B

Luogu
IDLGP8897
Time2000ms
Memory256MB
DifficultyP2
贪心USACO2022排序
Farmer John 计划为奶牛们新开办一所大学! ![](https://cdn.luogu.com.cn/upload/image_hosting/wiy5l6d6.png) 有 $N(1 \le N \le 10^5)$ 头奶牛可能会入学。每头奶牛最多愿意支付 $c_i$ 的学费 $(1 \le c_i \le 10^6)$。 Farmer John 可以设定所有奶牛入学需要支付的学费。如果这笔学费大于一头奶牛愿意支付的最高金额,那么这头奶牛就不会入学。Farmer John 想赚尽可能多的钱,从而可以给他的讲师提供一笔可观的工资。请求出他能赚到的钱的数量,以及此时应当收取多少学费。 ## Input 输入的第一行包含 $N$。 第二行包含 $N$ 个整数 $c_1,c_2, \cdots,c_N$,其中 $c_i$ 是奶牛 $i$ 愿意支付的最高学费金额。 ## Output 输出 Farmer John 可以赚到的最大金额以及最优情况下他应该收取的学费。如果有多个解,输出收取学费最小的解。 **注意这个问题涉及到的整数可能需要使用 64 位整数型(例如,Java 中的 "long",C/C++ 中的 "long long")。** [samples] ## Note ### 样例 1 解释 如果 Farmer John 收费 $4$,那么 $3$ 头奶牛将会入学,从而使他赚取 $3 \times 4=12$ 的金额。 ### 测试点性质 - 测试点 $2-4$ 满足 $c_i \le 1000$。 - 测试点 $5-8$ 满足 $N \le 5000$。 - 测试点 $9-12$ 没有额外限制。
Samples
Input #1
4
1 6 4 6
Output #1
12 4
API Response (JSON)
{
  "problem": {
    "name": "[USACO22DEC] Cow College B",
    "description": {
      "content": "Farmer John 计划为奶牛们新开办一所大学!  ![](https://cdn.luogu.com.cn/upload/image_hosting/wiy5l6d6.png) 有 $N(1 \\le N \\le 10^5)$ 头奶牛可能会入学。每头奶牛最多愿意支付 $c_i$ 的学费 $(1 \\le c_i \\le 10^6)$。 Farmer John 可以设定所有奶牛入学需要支付的学",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8897"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Farmer John 计划为奶牛们新开办一所大学! \n\n![](https://cdn.luogu.com.cn/upload/image_hosting/wiy5l6d6.png)\n\n有 $N(1 \\le N \\le 10^5)$ 头奶牛可能会入学。每头奶牛最多愿意支付 $c_i$ 的学费 $(1 \\le c_i \\le 10^6)$。 Farmer John 可以设定所有奶牛入学需要支付的学...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments