1052 地鼠游戲

?

?時間限制: 1 s ?空間限制: 128000 KB ?題目等級 : 鉆石 Diamond 題目描述?Description

? ? 王鋼是一名學習成績優異的學生，在平時的學習中，他總能利用一切時間認真高效地學習，他不但學習刻苦，而且善于經常總結、完善自己的學習方法，所以他總能在每次考試中得到優異的分數，這一切很大程度上是由于他是一個追求效率的人。

????但王鋼也是一個喜歡玩的人，平時在學校學習他努力克制自己玩，可在星期天他卻會抽一定的時間讓自己玩一下，他的爸爸媽媽也比較信任他的學習能力和學習習慣，所以在星期天也不會象其他家長一樣對他抓緊，而是允許他在星期天上午可以自由支配時間。

????地鼠游戲是一項需要反應速度和敏捷判斷力的游戲。游戲開始時，會在地板上一下子冒出很多地鼠來，然后等你用榔頭去敲擊這些地鼠，每個地鼠被敲擊后，將會增加相應的游戲分值。問題是這些地鼠不會傻傻地等你去敲擊，它總會在冒出一會時間后又鉆到地板下面去（而且再也不上來），每個地鼠冒出后停留的時間可能是不同的，而且每個地鼠被敲擊后增加的游戲分值也可能是不同，為了勝出，游戲參與者就必須根據每個地鼠的特性，有選擇地盡快敲擊一些地鼠，使得總的得分最大。

這個極具挑戰性的游戲王鋼特別喜歡，最近他經常在星期天上午玩這個游戲，慢慢地他不但敲擊速度越來越快（敲擊每個地鼠所需要的耗時是1秒），而且他還發現了游戲的一些特征，那就是每次游戲重新開始后，某個地鼠冒出來后停留的時間都是固定的，而且他記錄了每個地鼠被敲擊后將會增加的分值。于是，他在每次游戲開始后總能有次序地選擇敲擊不同的地鼠，保證每次得到最大的總分值。

輸入描述?Input Description

? ? 輸入包含3行，第一行包含一個整數n（1<=n<=100）表示有n個地鼠從地上冒出來，第二行n個用空格分隔的整數表示每個地鼠冒出后停留的時間，第三行n個用空格分隔的整數表示每個地鼠被敲擊后會增加的分值（<=100）。每行中第i個數都表示第i個地鼠的信息。

輸出描述?Output Description

? ? 輸出只有一行一個整數，表示王鋼所能獲得的最大游戲總分值。

樣例輸入?Sample Input

5

5??3??6??1??4

7??9??2??1??5

樣例輸出?Sample Output

24

/*貪心，按價值排序。然后從最大價值的時間往前找，能找到的加上就好了。 */ #include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #define MAXN 10010using namespace std; int n,ans; bool book[MAXN]; struct point{int w,t; }po[MAXN];bool cmp(point i,point j){return i.w>j.w;}int main(){int i,j,k;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&po[i].t);for(i=1;i<=n;i++)scanf("%d",&po[i].w); sort(po+1,po+n+1,cmp);for(i=1;i<=n;i++)for(j=po[i].t;j>=1;j--)if(!book[j]){book[j]=1;ans+=po[i].w;break; } cout<<ans;return 0;} 心若向陽，無言悲傷

?

轉載于:https://www.cnblogs.com/L-Memory/p/6241042.html

總結

以上是生活随笔為你收集整理的codevs地鼠游戏（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

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