posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

          PKU1042 – Gone Fishing

          Posted on 2007-10-17 17:25 ZelluX 閱讀(969) 評論(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
          主站蜘蛛池模板: 南宁市| 扎囊县| 兰州市| 漯河市| 滨州市| 靖州| 龙泉市| 中宁县| 滦平县| 那坡县| 磴口县| 海阳市| 丰顺县| 且末县| 河北区| 吐鲁番市| 北票市| 海阳市| 黑河市| 东辽县| 军事| 达州市| 宣恩县| 宝山区| 黄骅市| 汉阴县| 衢州市| 台东县| 方城县| 新安县| 东丽区| 桐乡市| 兴宁市| 弥勒县| 梅河口市| 开封县| 南丹县| 治县。| 遂平县| 恩平市| 福泉市|