1 条题解
-
1
#include <vector> #include <queue> #include <cstring> using namespace std; struct Node { int fish; int dec; int id; Node(int f, int d, int i) : fish(f), dec(d), id(i) {} bool operator<(const Node& other) const { // 大根堆:鱼多优先;鱼相同,编号小优先(满足字典序选左边时间更大) if(fish != other.fish) return fish < other.fish; return id > other.id; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; bool first_case = true; while(cin >> n && n != 0) { int H; cin >> H; int total_time = H * 12; // 总5分钟块 vector<int> f(n+1), d(n+1), t(n); for(int i = 1; i <= n; ++i) cin >> f[i]; for(int i = 1; i <= n; ++i) cin >> d[i]; for(int i = 1; i <= n-1; ++i) cin >> t[i]; int max_fish = -1; vector<int> best(n+1, 0); // best[i]:i号池塘花费多少个5分钟块 // 枚举最远到达k池塘 for(int k = 1; k <= n; ++k) { // 计算走到k需要走路时间 int walk = 0; for(int i = 1; i <= k-1; ++i) walk += t[i]; if(walk >= total_time) break; int fish_time = total_time - walk; // 可以用来钓鱼的5分钟块数量 priority_queue<Node> q; for(int i = 1; i <= k; ++i) { q.emplace(f[i], d[i], i); } vector<int> cnt(n+1, 0); // cnt[i]该方案下i池塘钓多少块 int sum = 0; for(int step = 0; step < fish_time; ++step) { auto cur = q.top(); q.pop(); sum += cur.fish; cnt[cur.id]++; int new_fish = max(0, cur.fish - cur.dec); q.emplace(new_fish, cur.dec, cur.id); } // 更新最优答案 if(sum > max_fish) { max_fish = sum; best = cnt; } } // 输出,注意组间空行 if(!first_case) cout << "\n"; first_case = false; // best转成分钟:*5 for(int i = 1; i <= n; ++i) { if(i > 1) cout << ", "; cout << best[i] * 5; } cout << "\nNumber of fish expected: " << max_fish << "\n"; } return 0; }
信息
- ID
- 1700
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 2
- 上传者