【題目】
題目背景
??? 在BIT的網(wǎng)絡(luò)教室里，有一位叫做大師的傳奇的人物。大師賣萌賣得好，黑人黑得好，寫(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是多么不容易啊，大家撿到一卡通錢包什么的一定要還給失主會(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)手。
