Gone Fishing 贪心算法

POJ 1042 Gone Fishing 贪心算法

2006-05-27　14:30:05

大　中　小

看上去比较难，看了报告分析就会觉得很简单了。贪心算法就能搞定，由于数据规模不大，因此每次都用遍历求最大值就能过了，但是我还是决定用堆去坐。普通遍历一次最大值复杂度O(N),用堆的话是O(logN)。以前不怎么用堆，这次也算用了呵呵。

 

题目: http://acm.pku.edu.cn/JudgeOnline/problem?id=1042

解体报告： http://zhaoyonghui.googlepages.com/POJ_1042.rar

 

代码如下：

/***************************************
 
   Author: 赵永辉
   Date:  2006.05.27

*****************************************/

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

#define min(a, b)  ((a) < (b) ? (a):(b))
#define max(a, b)  ((a) > (b) ? (a):(b))
#define INTMAX 1000000000
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

#define MAX 28
int n, h;
int d[MAX], t[MAX];
int temp[MAX], stay[MAX];
int i, j, r;
struct fish
{
  int f;
  int index;
  bool operator < (const fish &a) const
  {
   if(f < a.f)
    return true;
   else if(f == a.f)
    return index > a.index;
   else
    return false;
  }
};

fish f[MAX], now[MAX];
int ans, tans;
int  main()
{
 while(cin >> n && n)
 {
  ans = -1;
  cin >> h;
  for(i = 0;  i < n; i ++)
  {
   cin >> f[i].f;
   f[i].index = i;
  }
  for(i = 0;  i < n; i ++)
   cin >> d[i];

  t[0] = 0;
  for(i = 1;  i < n; i ++)
  {
   cin >> t[i];
   t[i] = t[i - 1] + t[i];
  }
  for(i = 1; i <= n; i ++)
  {
    memcpy(now, f, sizeof(f));
    memset(temp, 0, sizeof(temp));
    r = h*12 - t[i - 1];
    tans = 0;
    make_heap(now, now + i, less<fish>());
    for(j = 1; j <= r; j ++)
    {   
     if(now[0].f > 0)
        tans += now[0].f;
     now[0].f -= d[now[0].index];
     now[0].f = max(now[0].f, 0);
     temp[now[0].index] += 5;
     pop_heap(now, now + i, less<fish>());
     push_heap(now, now + i, less<fish>());    
    }
    if(tans > ans)
    {
     ans = tans;
     memcpy(stay, temp, sizeof(stay));
    }  
  }
        for(i = 0; i < n - 1; i ++)
   cout << stay[i] <<", ";
  cout << stay[n - 1] << endl;
  cout <<"Number of fish expected: "<< ans <<endl << endl;  
 }
 return 0;  
}