ZOJ 3519 Who is the Smartest Man（水水的贪心）

布满荆棘的人生 2022-06-10 02:56 225阅读 0赞

[Cao Cao][] is very pround of his newly finished book named "The Book of Mengde". He thinks the book contains all the wisdom of the world. But in order to prove this, he need to prove that he is the smartest people in the world first. In that age, people evaluate the intelligence of a man by his eloquence. So, [Cao Cao][] begins to make a plan to argue with some famous person, like Guo Jia, Xun Yu and so on. Soon he realizes that the hardest opponent is Zhuge Liang. So he decide to make it the last opponent. Once he defeat Zhuge Liang in the argument. he will be consider the smartest man in the world and his book will be the best book.

![ae9ae220fc94c7da19f2d5812f028409_v_1502166283][]

Now, Cao Cao knows the intelligent point of himself and everyone he want to argue with before Zhuge Liang. And he knows that if he wins an argument.His intelligent point will increase because he can learn something from the argument. If he defeats a opponent whose intelligent point is higher than his, his intelligent point will increase by 2. If the intelligent point of the opponent is not higher than his, his intelligent point will only increase by 1.

Now,[Cao Cao][] wants to know, what's the maximum intelligent point he could reach before he meets Zhuge Liang, assuming that he can win each argument before he meets Zhuge Liang.

Input

The first line of each case contains two postive integer *N*(*N* <= 500) and *IP*. *N* is the number of people [Cao Cao][] wants to argue with before he meets Zhuge Liang. *IP* is the intelligent point of Cao Cao at the begining. Then *N* postive integers followed describing the intelligent point of each opponent. Each intelligent point will be no higher than 1000.

Output

For each case, output the maximum intelligent point [Cao Cao][] can reach before he argue with Zhuge Liang.

Sample Input

5 91
    88 90 92 94 98

Sample Output

题解：

题意：

曹老大最终要和亮仔比智商，已知初始智商，和群臣智商，曹老大每和比自己高的人比智商+2，如果等于或者低于自己的就智商+1，问与群臣比完最终智商能为多少

ps：

我觉得做出这题会降智商hhhhh

思路：

很简单的贪心，就是将群臣的智商排序，曹老大开始和刚刚好比自己高的大臣比，然后往后面扫，遇到比自己低的或者相同的就留着以后比，直到找到比自己智商高的为止

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    using namespace std;
    int a[505];//存智商
    int main()
    {
        int st,i,j,ans,n;
        while(scanf("%d%d",&n,&st)!=EOF)
        {
            for(i=0;i<n;i++)
                scanf("%d",&a[i]);
            sort(a,a+n);//智商排序
            i=0;
            while(i<n&&a[i]<st)//找到一个刚好比曹老大聪明点的
                i++;
            if(i==n)//如果已经无敌了
            {
                printf("%d\n",st+n);
                continue;
            }
            else//从这里开始比
            {
                ans=i;
                int temp=0;
                for(j=i;j<n;j++)
                {
                    if(a[j]>st)
                    {
                        st+=2;
                    }
                    else//没比曹老大聪明，以后再比，留在temp里
                    {
                        temp+=1;
                    }
                }
                st+=ans;//加上之前不必曹老大聪明的人
                st+=temp;//加上之后不比曹老大聪明的人
            }
            printf("%d\n",st);
        }
        return 0;
    }

[Cao Cao]: http://zh.wikipedia.org/wiki/%E6%9B%B9%E6%93%8D
[ae9ae220fc94c7da19f2d5812f028409_v_1502166283]: https://odzkskevi.qnssl.com/ae9ae220fc94c7da19f2d5812f028409?v=1502166283