【題目】

題目背景

在BIT的網絡教室里，有一位叫做大師的傳奇的人物。大師賣萌賣得好，黑人黑得好，寫代碼更是一絕。她在輕松AC了題目之后還要故意重新交幾次默默刷高自己的罰分使自己排名靠后以深藏功與名，但是由于大師壓倒性的實力，她還是并列了網教的第一。在一個叫什么什么M的神秘組織里，大師的代號是07。

大師的RP值一向很高，然而，由于最近她聯合了YW大神在網教里黑掉了無辜的渣渣，大師的RP值驟減(黑人是要掉RP的哦~)。期末考試臨近，大師想以一個高RP狀態去參加考試(其實吧即使大師的RP為0也能拿滿分)，于是大師決定周五上午到理教201在陳老師的C語言課上收集RP。

那么大師是怎樣獲取RP的呢？她有一個獨特的技能——「嚶嚶」。美麗的大師坐到你身旁，用她那水汪汪的眼睛望著你，然后———— ”>.

現在已知陳老師的課堂里有N位無辜的同學/老師(不排除鷹哥被嚶嚶的可能性= =)，每個人有一個固定的RP值rp[i]，大師會對Ta們使出嚶嚶技能。大師每對一個RP比自己低的人(例如李渣渣)使出嚶嚶，大師會獲得1點RP值，每對一個RP值大于等于自己RP的人使出嚶嚶，大師會獲得2點RP。(大師說：賺RP是多么不容易啊，大家撿到一卡通錢包什么的一定要還給失主會獲得大量RP噠)。機智的大師當然會安排一個最佳的方案使得自己達到最高的RP。

大師收集完RP之后要去和渣渣玩兒猜拳。渣渣想知道大師最多能獲得多少RP以估測自己獲勝的幾率。然而由于渣渣的IQ非常捉雞，他找到了聰明的你，請你幫渣渣計算一下大師的RP能夠達到的最大值。

PS:大師,YW大神和渣渣祝大家端午節快樂~

題目作者

渣渣

輸入

第一行：一個數字N (0

第二行：一個數字R (0<=R<=10000)，代表大師的初始RP值。

第三行：N個正整數，代表每個人的RP值(0<=rp[i]<=10000)。

輸出

大師能夠達到的最高的RP

輸入樣例

5

100

90 100 80 120 100

輸出樣例

107

測試輸入期待的輸出時間限制內存限制額外進程

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?

【題目分析】初讀該題， 大概對此題有一個基本理解：首先一個人A有一個初始的RP值r，同時，他的身邊有N個人， 他們各自也有相應的rp值，A遇到一個rp值大于等于自己的人，自己的RP便會+2(在后面我們會把這個操作成為吸2點RP)，否則RP+1，顯而易見，A的RP是非增的。題目的目的是使A擁有最大的RP值，這是一個典型的貪心問題(我們可以通過求出各個子問題的最優解得到整個問題的最優解，有的問題看似是貪心，但貪心沒有辦法得到最優的結果，例如01背包問題，還有大家熟知的將軍飲馬問題)。所以，我們想讓A的RP值達到最大，我們只需讓他的RP值盡量多的+2，故我們首先要去尋找RP值大于等于A的，從小到大依次吸(在這里我們為什么從小到大吸，其原因舉個例子便顯而易見。比如現在A的初始RP是100，旁邊有幾個人，他們的RP分別是100， 100， 102，假如你先吸102，那么這之后A的RP便是102， 剩下的兩個100只能各自吸1，得到的最大RP值只能是102+1+1=104，而如果我們先吸一個RP為100的，再吸一個RP為102的，那么我們此時的RP可以達到100+2+2+1=105，容易證明這是最優解)。要注意的是，我們此時的從小到大吸指的是rp大于A初始RP的人從小到大排序。

【題目難點】

其實這是一道貪心+排序題(當然不學計算機專業的話也沒必要知道這是貪心問題，只需了解這個問題就是將整個問題內所有自問題均尋求出它們的最優解即可)，并沒有什么難點。在這里寫一寫簡單的偽代碼。

【C語言代碼】

#include

#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

for(int j=0;j

if(rp[j]

int t=rp[j+1];

rp[j+1]=rp[j];

rp[j]=t;

}

}

}

for(int i=0;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】

剛開始的時候我以為這個題需要按順序依次計算， 故對于每一個rp[i]都有選或者不選兩種可能，顯然復雜度為O(2^N)，用dp寫了半天，dalao悠悠地告訴我這是貪心。。。所以吧，還是寫代碼前先好好想想，別著急動手。

總結

以上是生活随笔為你收集整理的北理乐学c语言答案猴子,【北理乐学】机智的大师的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。