uva-757-贪心-白红宇

uva-757-贪心

阅读量：7222 次

发布时间：2019-06-29

本文共 2318 字，大约阅读时间需要 7 分钟。

题意：有个人要去湖里钓鱼,总共有N个湖,排成一个序列,用字母P表示湖，从湖pi 到 pi+1(下一个湖)需要ti个五分钟.

并且，每个湖里可钓出来的鱼每过五分钟就减少di.如果产出的鱼小于等于di.那么下个五分钟这个湖再也不会产出鱼.

问:使得总的钓出鱼数目最大和每个湖花费的对应时间,.如果鱼数目最大存在多种解,让时间尽可能花费在前面的湖上.

解法：

枚举每一个pi,划去从p0至pi的总time(总的转移时间).

这样我们就可以在任意p0-pi之间钓鱼而不用考虑time的问题.剩下的h全部花费在钓鱼上.

每次花费的五分钟都花在产出鱼数目最大的湖上.这样得到总鱼数目总是最大的.如果所有的鱼都钓完还有时间剩余.全部加在第一个湖上面.

#include 
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include"math.h"namespace cc{ using std::cout; using std::endl; using std::cin; using std::map; using std::vector; using std::string; using std::sort; using std::priority_queue; using std::greater; using std::vector; using std::swap; using std::stack; using std::queue; using std::bitset; class State { public: int curFish; int d; int time; int index; State() {} State(int curFish, int d, int time, int index) : curFish(curFish), d(d), time(time), index(index) { } friend bool operator < (const State& s1, const State& s2) { if (s1.curFish != s2.curFish) return s1.curFish < s2.curFish; return s1.index > s2.index; } }; constexpr int N = 32; int H = 0; int n; int totalFish; int per[N] = { 0 }; State states[N]; priority_queue < State>q; void solve() { int t = 0; while (cin >> n && n) { if (t != 0) cout << endl; ++t; cin >> H; H = H * 12; int f = 0; for (int i = 0;i < n;i++) { cin >> f; State state(f, 0, 0, i); states[i] = state; } for (int i = 0;i < n;i++) { cin >> states[i].d; } for (int i = 1;i < n;i++) { cin >> states[i].time; states[i].time = states[i].time + states[i-1].time; } totalFish = -1; memset(per, 0, sizeof(per)); for (int i = 0;i < n;i++) { while (q.empty() == false) q.pop(); for (int k = 0;k <= i;k++) q.push(states[k]); int h = H; int curTotalFish = 0; int times[N] = { 0}; h = h - states[i].time; while (h > 0) { State s = q.top(); q.pop(); int f = s.curFish; if (f <= 0)break; --h; s.curFish -= s.d; curTotalFish += f; times[s.index]++; q.push(s); } if (h > 0) times[0] += h; if (curTotalFish > totalFish) { totalFish = curTotalFish; memcpy(per, times, sizeof(times)); } } cout << per[0] * 5; for (int i=1;i

posted on

2019-03-03 11:47 阅读(

...) 评论(

...)

转载于:https://www.cnblogs.com/shuiyonglewodezzzzz/p/10464528.html

你可能感兴趣的文章