1139

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 425  Solved: 129

[Submit][Status][Web Board]

Description

松哥上了数学课之后，觉得自己智力实在有所不足，所以他决定找人辩论，以提高自己的智力，已知松哥目前的智力是m，他决定和n个人辩论，如果他对手的智力高于他，松哥的智力能够提升2，否则只能提升1，假设松哥能够取得所有的胜利，请问他完成n场辩论后能够得到的最高智力是多少？

Input

多组测试数据.

每组测试数据的第一行包含两个正整数m,n.(m<=100,n<=10^5)

第二行为n个不大于100的整数，代表与他辩论人的智力.

Output

对于每组测试数据，他完成n场辩论后，能取得的最大的智力.

Sample Input

91 5

88 90 92 94 98

Sample Output

99

HINT

Source

---

ZCMU-1139: 松哥的困惑V && ZCMU-1143:又是比智力（贪心） - waterboy_cj的博客 - CSDN博客

因为对手高于他才能得分，那么输入进去的低分记住个数（num_low）就行了，答案里记得加上，就OKK。智力比他高的，需要存数组里。然后很自然的排序（为了智力提升最大化），高的+2，不高于的+1;

---

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int main()

{

int m, n, a[N];

while (~scanf("%d%d", &m, &n))

{

int t,num_low = 0, len_high = 0;

for (int i = 0; i < n; i++)

{

scanf("%d", &t);

if (t <= m)//低智力直接记个数

num_low++;

else   //高智力存入数组

{

a[len_high] = t;

len_high++;

}

}

sort(a, a + len_high);//排序

int score_fail = 0;

for (int i = 0; i < len_high; i++)

{

if (m < a[i])m += 2;

else

score_fail++;//不能直接m++因为这样会影响下一次循环。你就想反正得不到2

//那到最后再得1好了，直接+1可能会让你下一次得不到2

}

printf("%d\n", m + num_low + score_fail);

}

return 0;

}