Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

PKU1042 – Gone Fishing

Posted on 2007-10-17 17:25 ZelluX 阅读(836) 评论(5)  编辑  收藏 所属分类: Algorithm

我的做法是枚举最远到达的湖,减去相应的时间后贪心。

贪心时需要建立一个堆,用了STL中的priority_queue,然后就不知道如何设置less<>方法了。。。
最后是通过自定义一个类node解决的

一开始写的operator<方法逻辑上有问题,VS 2005跑了一会儿就冒出个 Debug assert error,这个挺赞的

导致我WA的几个数据:
1) 收益为0的几组数据。由于一开始设置的max值为0,因此当正解也是0时并没有记录下当前的最优解。max初始为负值即可。
2) 同样是0导致的问题。0收益的钓鱼点也可能出现在堆中,此时应该放弃这个点,把时间保留给序数大的钓鱼点。

另外我有这次比赛的测试数据和标程,需要的朋友留言即可。


 

#include <iostream>
#include 
<fstream>
#include 
<vector>
#include 
<queue>

using namespace std;

class node {
public
    
int first, second;

    node(
int x, int y)
    
{
        first 
= x;
        second 
= y;
    }


    
bool operator< (const node &rhs) const
    
{
        
if (second < rhs.second) 
            
return true;
        
else if (second > rhs.second)
            
return false;
        
else return (first > rhs.first);
    }

}
;


int main()
{
    
int n, h;
    
int d[26], t[26], f[26];
    priority_queue
<node, vector<node>, less<vector<node>::value_type> > heap;
    vector
<int> best(26);
    cin 
>> n;
    
while (true{
        
if (n == 0break;
        cin 
>> h;
        
for (int i = 1; i <= n; i++)
            cin 
>> f[i];

        
for (int i = 1; i <= n; i++)
            cin 
>> d[i];

        t[
0= 0;
        
for (int i = 1; i < n; i++)
            cin 
>> t[i];

        best.clear();
        
int max = -1;
        
// i indicates the last lake
        for (int i = 1; i <= n; i++{
            vector
<int> tempBest(26);
            
int valueGet = 0;
            
            
int timeLeft = h * 12;
            
for (int j = 1; j <= i; j++)
                timeLeft 
-=    t[j - 1];

            
if (timeLeft <= 0break;
            
while (!heap.empty())
                heap.pop();

            
for (int j = 1; j <= i; j++)
                heap.push(node(j, f[j]));

            
while ((!heap.empty()) && (timeLeft > 0)) {
                
int next = heap.top().first;
                
if (heap.top().second > 0{
                    timeLeft
--;
                    tempBest[next]
++;
                    valueGet 
+= heap.top().second;
                }

                
int valueLeft = heap.top().second - d[next];
                heap.pop();
                
if (valueLeft > 0)
                    heap.push(node(next, valueLeft));
            }

            
if (valueGet > max) {
                max 
= valueGet;
                best 
= tempBest;
                
if (timeLeft > 0)
                    best[
1+= timeLeft;
            }

        }

        printf(
"%d", best[1* 5);
        
for (int i = 2; i <= n; i++)
            printf(
", %d", best[i] * 5);
        printf(
"\nNumber of fish expected: %d\n", max);
        cin 
>> n;
        
if (n != 0) cout << endl;
    }

    
return 0;
}


评论

# re: PKU1042 – Gone Fishing  回复  更多评论   

2007-11-20 23:00 by 风木草
lrx_919@yahoo.com.cn
发一份测试数据给我,谢谢!

# re: PKU1042 – Gone Fishing  回复  更多评论   

2007-11-23 20:40 by ZelluX
这里有
http://icpc.baylor.edu/past/icpc2000/regionals/ECNA99/Report.html

# re: PKU1042 – Gone Fishing  回复  更多评论   

2008-07-16 23:19 by kevin***
我只要测试数据啊,请发一份给我,谢谢


380061431@qq.com

# re: PKU1042 – Gone Fishing[未登录]  回复  更多评论   

2008-09-27 20:18 by johnson
发一份测试数据给我,谢谢!
173125256@qq.com

# re: PKU1042 – Gone Fishing  回复  更多评论   

2009-04-06 19:08 by Blade
要一份测试数据,谢谢
lanefeng1989@163.com

只有注册用户登录后才能发表评论。


网站导航: