1 条题解

  • 1
    @ 2026-9-7 20:40:54
    #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
    上传者