貪心法 codevs 1052 地鼠遊戲

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

分析：

這道題目就是一個簡單的貪心：正确的貪心法：一.在有限的時間内敲掉更多分值大的。二.把每一秒都利用起來（盡量讓每一隻地鼠都在即将消失的那一秒被砸中。這樣占用其他的資源就少。）

這個貪心的正确性很顯然。

我的錯誤之處：沒有正确分析好貪心，沒有處理好先打分數大和先把一分鐘都利用起來。隻得了30分。

1 #include<algorithm>
 2 #define T 1000000/*保證T*N不超過一秒的理論最大值*/
 3 #include<iostream>
 4 using namespace std;
 5 #include<cstdio>
 6 int n,ans=0;
 7 bool visit[T];
 8 struct Ds{
 9     int val,tim;
10     bool operator<(Ds P)
11     const{return val>P.val;}
12 }ds[101];
13 int main()
14 {
15     scanf("%d",&n);
16     for(int i=1;i<=n;++i)
17       scanf("%d",&ds[i].tim);
18     for(int i=1;i<=n;++i)
19       scanf("%d",&ds[i].val);
20     sort(ds+1,ds+n+1);
21     for(int i=1;i<=n;++i)
22     {
23         int t=ds[i].tim;
24         while(visit[t]) t--;
25         if(t==0) continue;
26         visit[t]=true;
27         ans+=ds[i].val;
28     }
29     printf("%d\n",ans);
30     return 0;
31  }