1449. [USACO Mar]参加考试

【题目描述】

Farmer John要参加一年一度的农民资格考试。考试很简单，只有N个 （1≤N≤1，000，000)true/false的判断题。然而FJ去年考试却“杯具”了，Bessie：希望今年能帮帮他。

Bessie得到可靠的内部消息，有可能有T_1，T_2，T_3，...，或T_K(0≤T_i≤N；0≤K≤10，000)

道题的答案为ture：，但具体哪道题的答案是什么却不知道。Bessie希望知道在认真研究了这些内部消息后(虽然不能确定任何一道题的具体答案)，一定保证FJ考试时能获得的最高分数是多少?

为了说明Bessie的想法，考虑N=6的一次考试，Bessie知道答案为true的题的数量是0或者3。FJ可以按这样的做题策略来答对至少3题：如果FJ全部答'false'，那么当有0道题的正确答案是'true'，则FJ答对6题；而当有3道题的正确答案是'true'，则FJ答对3题。因此，只要FJ部答'false'，那么至少一定能答对3题，尽管FJ并不知道每道题的确切答案。

另一方面，考虑如果FJ选择了另一种非最优的做题策略：他猜测某3道题为'true'而另3道题为'false'。当所有题目的正确答案是'false'时，那么FJ能答对3道题。而当有3道题的正确答案是'true'时，那么FJ有可能一道题都答不对。这是因为FJ有可能把3道正确答案为'true'的题全猜成'false'!这说明这种做题策略不如前一种优秀。

给出Bessie获得的内部消息，计算出FJ采用最优做题策略保证能得到的最高分数是多少?

【输入格式】

第1行：2个整数N，K

第2…K+1行：第i+1行包含一个整数t_i

【输出格式】

第1行：一个整数，表示FJ一定能获得的最高分数

【样例输入】

6 2
0
3

【样例输出】

3

【提示】

在此键入。

【来源】

在此键入。