Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

poj-1042 Gone Fishing **

来源: 未知 分享至:
/*  贪心+优先级队列
*
* 贪心:为了不讨论在路上花费的时间,可以枚举到过的湖:比如:totLake=j 表示 到过湖1、2、..、j 相应的, 花在路上的时间
* 就是 t[1]+t[2]+..+t[j-1] (显然每段路只会走一次) 于是算出leftTime,表示花在钓鱼上的时间
* 这样一来,就不同再考虑路上的时间了,可以认为John有瞬间移动,哪个湖鱼多,就到哪个湖钓(当然 湖的编号 满足 1 <= ~ <=totLake )
*
* 于是可以用一个优先级队列,每次到与最多的湖钓,
* 还要注意的是,如果某时刻有多个湖有同样多的鱼,则到湖编号最小的那个湖里钓!!(只要对优先级队列做相应的修改)
* 用二叉堆实现优先级队列
*
* 最后注意ans == 0的情况
* 看数据:
* 2
* 1
* 0 0
* 1 1
* 1
* 答案:
* 60 0
* 0
*/

#include
<cstdio>
#include
<cstring>
using namespace std;

const int maxN = 25 + 2, inf = 100000;
int n, h, f[maxN], d[maxN], t[maxN]; //如题所述
int timeOnLake[maxN], totLake, ans, ansTimeOnLake[maxN];

int heap[maxN], key[maxN]; //heap【】:该节点的湖编号。。key【】:该节点当前的能钓到的鱼数


void ini(){
for(int i=1; i<=totLake; i++){
heap[i]
= i; key[i] = f[i];
}
memset(timeOnLake,
0, sizeof(timeOnLake));
}

int inline left(int i){ return i*2; }
int inline right(int i){ return i*2+1; }
int inline p(int i){ return i/2; }

void inline swap(int x, int y){
int tmp;
tmp
= heap[x]; heap[x] = heap[y]; heap[y] = tmp;
tmp
= key[x]; key[x] = key[y]; key[y] = tmp;
}

void max_heapify(int i, int tot){
int imax = i;
int l = left(i);
int r = right(i);

//注意做相应的修改。。key相同时,湖编号小的优先级高
if(l <= tot && (key[l] > key[imax] || (key[l]==key[imax] && heap[l] < heap[imax])))
imax
= l;
if(r <= tot && (key[r] > key[imax] || (key[r]==key[imax] && heap[r] < heap[imax])))
imax
= r;

if(imax != i){
swap(i, imax);
max_heapify(imax, tot);
}
}
//建堆
void build_max_heap(){
for(int i=totLake/2; i>=1; i--){
max_heapify(i, totLake);
}
}
//弹出最大元
int heap_extract_max(int &lakeNum, int &tot){

Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史