【題目】
題目背景
??? 在BIT的網(wǎng)絡(luò)教室里狐肢，有一位叫做大師的傳奇的人物。大師賣(mài)萌賣(mài)得好沥曹，黑人黑得好份名，寫(xiě)代碼更是一絕碟联。她在輕松AC了題目之后還要故意重新交幾次默默刷高自己的罰分使自己排名靠后以深藏功與名，但是由于大師壓倒性的實(shí)力同窘，她還是并列了網(wǎng)教的第一玄帕。在一個(gè)叫什么什么M的神秘組織里部脚，大師的代號(hào)是07想邦。
??? 大師的RP值一向很高，然而委刘，由于最近她聯(lián)合了YW大神在網(wǎng)教里黑掉了無(wú)辜的渣渣丧没，大師的RP值驟減（黑人是要掉RP的哦~）。期末考試臨近锡移，大師想以一個(gè)高RP狀態(tài)去參加考試（其實(shí)吧即使大師的RP為0也能拿滿分）呕童，于是大師決定周五上午到理教201在陳老師的C語(yǔ)言課上收集RP。
?? 那么大師是怎樣獲取RP的呢淆珊？她有一個(gè)獨(dú)特的技能——「嚶嚶」夺饲。美麗的大師坐到你身旁，用她那水汪汪的眼睛望著你施符，然后———— ”>.<嚶嚶~” 使你不忍心不分給她一些RP往声。
??? 現(xiàn)在已知陳老師的課堂里有N位無(wú)辜的同學(xué)/老師（不排除鷹哥被嚶嚶的可能性= =），每個(gè)人有一個(gè)固定的RP值rp[i]戳吝，大師會(huì)對(duì)Ta們使出嚶嚶技能。大師每對(duì)一個(gè)RP比自己低的人（例如李渣渣）使出嚶嚶，大師會(huì)獲得1點(diǎn)RP值杖挣，每對(duì)一個(gè)RP值大于等于自己RP的人使出嚶嚶伸头，大師會(huì)獲得2點(diǎn)RP。（大師說(shuō)：賺RP是多么不容易啊陆盘，大家撿到一卡通錢(qián)包什么的一定要還給失主會(huì)獲得大量RP噠）普筹。機(jī)智的大師當(dāng)然會(huì)安排一個(gè)最佳的方案使得自己達(dá)到最高的RP。
大師收集完RP之后要去和渣渣玩兒猜拳隘马。渣渣想知道大師最多能獲得多少RP以估測(cè)自己獲勝的幾率太防。然而由于渣渣的IQ非常捉雞，他找到了聰明的你祟霍，請(qǐng)你幫渣渣計(jì)算一下大師的RP能夠達(dá)到的最大值杏头。
PS:大師,YW大神和渣渣祝大家端午節(jié)快樂(lè)~
題目作者
?渣渣
輸入
第一行：一個(gè)數(shù)字N (0
第二行：一個(gè)數(shù)字R (0<=R<=10000)，代表大師的初始RP值沸呐。
第三行：N個(gè)正整數(shù)醇王，代表每個(gè)人的RP值(0<=rp[i]<=10000)。
輸出
??? 大師能夠達(dá)到的最高的RP
輸入樣例
5
100
90 100 80 120 100
輸出樣例
107
?測(cè)試輸入期待的輸出時(shí)間限制內(nèi)存限制額外進(jìn)程
Input1：
5?
100?
90?100?80?120?100?
Output1：
107?
Input2：
10?
12?
1?9?6?19?11?16?10?6?15?16?
Output2：
26?
【題目分析】初讀該題崭添， 大概對(duì)此題有一個(gè)基本理解：首先一個(gè)人A有一個(gè)初始的RP值r寓娩，同時(shí)，他的身邊有N個(gè)人， 他們各自也有相應(yīng)的rp值棘伴，A遇到一個(gè)rp值大于等于自己的人寞埠，自己的RP便會(huì)+2（在后面我們會(huì)把這個(gè)操作成為吸2點(diǎn)RP），否則RP+1焊夸，顯而易見(jiàn)仁连，A的RP是非增的。題目的目的是使A擁有最大的RP值阱穗，這是一個(gè)典型的貪心問(wèn)題（我們可以通過(guò)求出各個(gè)子問(wèn)題的最優(yōu)解得到整個(gè)問(wèn)題的最優(yōu)解饭冬，有的問(wèn)題看似是貪心，但貪心沒(méi)有辦法得到最優(yōu)的結(jié)果揪阶，例如01背包問(wèn)題昌抠，還有大家熟知的將軍飲馬問(wèn)題）。所以鲁僚，我們想讓A的RP值達(dá)到最大炊苫，我們只需讓他的RP值盡量多的+2，故我們首先要去尋找RP值大于等于A的冰沙，從小到大依次吸（在這里我們?yōu)槭裁磸男〉酱笪劝湓蚺e個(gè)例子便顯而易見(jiàn)。比如現(xiàn)在A的初始RP是100倦淀，旁邊有幾個(gè)人蒋畜，他們的RP分別是100， 100撞叽， 102姻成，假如你先吸102，那么這之后A的RP便是102愿棋， 剩下的兩個(gè)100只能各自吸1科展，得到的最大RP值只能是102+1+1=104，而如果我們先吸一個(gè)RP為100的糠雨，再吸一個(gè)RP為102的才睹，那么我們此時(shí)的RP可以達(dá)到100+2+2+1=105，容易證明這是最優(yōu)解）甘邀。要注意的是琅攘，我們此時(shí)的從小到大吸指的是rp大于A初始RP的人從小到大排序。
【題目難點(diǎn)】
其實(shí)這是一道貪心+排序題（當(dāng)然不學(xué)計(jì)算機(jī)專業(yè)的話也沒(méi)必要知道這是貪心問(wèn)題松邪，只需了解這個(gè)問(wèn)題就是將整個(gè)問(wèn)題內(nèi)所有自問(wèn)題均尋求出它們的最優(yōu)解即可）坞琴，并沒(méi)有什么難點(diǎn)。在這里寫(xiě)一寫(xiě)簡(jiǎn)單的偽代碼逗抑。
【C語(yǔ)言代碼】
#include <stdio.h>
#define maxn 1005
int rp[maxn];
int main() {
? ? int n, r, sign=0;
? ? scanf("%d%d", &n, &r);
? ? for (int i = 0; i < n; i++)
? ? ? ? scanf("%d", &rp[i]);
? ? for(int i=0;i<n-1;i++){
? ? ? ? for(int j=0;j<n-i;j++){
? ? ? ? ? ? if(rp[j]<rp[j+1]){
? ? ? ? ? ? ? ? int t=rp[j+1];
? ? ? ? ? ? ? ? rp[j+1]=rp[j];
? ? ? ? ? ? ? ? rp[j]=t;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? for(int i=0;i<n-1;i++){
? ? ? ? if(rp[i]>=r&&rp[i+1]<=r)
? ? ? ? ? ? sign=i;
? ? }
? ? for(int i=sign;i>=0;i--){
? ? ? ? if(rp[i]>=r)? ? r+=2;
? ? ? ? else? ? r++;
? ? }
? ? r += n - sign - 1;
? ? printf("%d\n",r);
? ? return 0;
}
【Hint】
剛開(kāi)始的時(shí)候我以為這個(gè)題需要按順序依次計(jì)算剧辐， 故對(duì)于每一個(gè)rp[i]都有選或者不選兩種可能寒亥，顯然復(fù)雜度為O(2^N)，用dp寫(xiě)了半天荧关，dalao悠悠地告訴我這是貪心溉奕。。忍啤。所以吧加勤，還是寫(xiě)代碼前先好好想想，別著急動(dòng)手檀轨。
