1143: 又是比智力

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 1578  Solved: 291

[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

101

HINT

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

有点类似田忌赛马，我要是比不过你，那我就去找最厉害的人比，反正都是输，先输给厉害的人，说不定下次就能比你高1。

#include<bits/stdc++.h>

using namespace std;

int main()

{

std::ios::sync_with_stdio(false);//budong

int m,n,nn[100100];

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

memset(nn,0,sizeof(nn));

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

scanf("%d",&nn[i]);

sort(nn,nn+n);

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

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

else

{

n--;

i--;

m++;

}

}

printf("%d\n",m);

}

return 0;

}