POJ1042 贪心钓鱼
题意:
你有H小时(H*12个单位)时间去用,有n个鱼池在一条直线上,一开始你在1的位置,可以选择在某些鱼池上钓鱼,但是如果持续在一个鱼池上钓鱼钓鱼速度回成线性减少,初始每个时间单位钓fi条,然后下一个时间单位钓fi-di条,再下一个fi-di-di条,每个鱼池和他下一个鱼池的距离是ti个时间单位,最后你可以听到任意一个鱼池上,问最多钓多少条鱼,然后输出在个鱼池的停留时间和最多的鱼数。
思路:
枚举终点,对于每一个枚举的终点也就是相当于拥有了一段可以随意选的鱼塘,然后我们在枚举区间没一个单位一个单位的去选,每次都去选最优的一个,然后加到总和里,然后把当前这个鱼塘的速度改变下,这里可以用优先队列去实现,每次拿出一个最优的,然后更新总和,然后把拿出来这个更改数值后存回队列,还有就是注意输出要求,答案不确定的时候输出什么啥的一些小细节。
#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef struct NODE
{
int id ,f ,d;
friend bool operator < (NODE a ,NODE b)
{
return a.f < b.f || a.f == b.f && a.id > b.id;
}
}NODE;
int main ()
{
int n ,h ,i ,j ,sum ,tsum;
int ans[30] ,tans[30];
int tt[30];
NODE node[30];
int mk = 0;
while(~scanf("%d" ,&n) && n)
{
if(mk) printf("\n");
mk = 1;
scanf("%d" ,&h);
for(i = 1 ;i <= n ;i ++)
{
scanf("%d" ,&node[i].f);
node[i].id = i;
}
for(i = 1 ;i <= n ;i ++)
scanf("%d" ,&node[i].d);
for(i = 1 ;i < n ;i ++)
scanf("%d" ,&tt[i]);
memset(ans ,0 ,sizeof(ans));
sum = -1;
int s = 0;
h *= 12;
for(i = 1 ;i <= n ;i ++)
{
if(i == 1) s = 0;
else s += tt[i-1];
if(s > h) break;
priority_queue<NODE>q;
NODE xin ,tou;
for(j = 1 ;j <= i ;j ++)
q.push(node[j]);
int hh = h - s;
memset(tans ,0 ,sizeof(tans));
tsum = 0;
while(hh--)
{
tou = q.top();
q.pop();
tans[tou.id] += 5;
tsum += tou.f;
tou.f -= tou.d;
if(tou.f < 0) tou.f = 0;
q.push(tou);
}
if(tsum > sum)
{
for(j = 1 ;j <= n ;j ++)
ans[j] = tans[j];
sum = tsum;
}
}
for(i = 1 ;i <= n ;i ++)
{
if(i == n) printf("%d\n" ,ans[i]);
else printf("%d, ",ans[i]);
}
printf("Number of fish expected: %d\n" ,sum);
}
return 0;
}
最新文章
- Ajax入门(三)
- keep the bar green to keep the code clean——Junit详解(二)
- C#,.Net自动生成大写字母编码
- Linq To Sql多表联合查询
- 用ubuntu下载电影:磁力链接,torrent,迅雷链接
- Android基础总结(7)——异步消息处理
- class-dump 复制到/usr/bin目录不可写,Operation not permitted 解决办法
- svn删除目录后提交显示Item &#39;XXXX&#39; is out of date解决方法
- Delphi调试CGI或ISAPI 转
- HDU2138 随机素数测试 Miller-Rabin算法
- eclipse设置java虚拟机内存大小
- bootstrap 预定义样式风格
- 同步请求和异步请求的区别,ajax异步请求如何理解
- Myeclipse调试模式下自动提示变量值设置
- Terminating app due to uncaught exception &#39;NSInvalidArgumentException&#39;, reason: &#39;*** -[__NSPlaceholderDictionary initWithObjects:forKeys:count:]: attempt to insert nil object from objects[0]&#39;
- 1:Javascript的数据类型和相互转换
- Utils--Cookie工具类
- Group by与 having
- C# 监测每个方法的执行次数和占用时间(测试1)
- 将Unity导出的Eclipse工程转换为AndroidStudio工程