求问用优先级队列做的为什么不对
查看原帖
求问用优先级队列做的为什么不对
783751
Tok1楼主2024/1/23 17:01
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
struct pile
{
    int weight;
    int value;
    double per;
    friend bool operator<(const pile &pile1, const pile &pile2)
    {
        return pile1.value * pile2.weight > pile2.value * pile1.weight;
    }
};
priority_queue<pile> q;

int main()
{
    int N, T;
    scanf("%d %d", &N, &T);
    const int NUMBERS = N;
    pile piles[NUMBERS];

    int weights = 0;
    double values = 0;
    for (int i = 0; i < N; ++i)
    {
        int m, v;
        scanf("%d %d", &m, &v);
        piles[i].weight = m;
        piles[i].value = v;
        piles[i].per = (1.0 * v) / m;

        q.push(piles[i]);

        weights += m;
        values += v;

        while (weights > T)
        {
            pile top_pile = q.top();

            if (weights - top_pile.weight >= T)
            {
                q.pop();
                weights -= top_pile.weight;
                values -= top_pile.value;
            }
            else
            {
                top_pile.weight -= weights - T;
                values -= top_pile.per * (weights - T);
                weights = T;
            }
        }
    }

    printf("%.2lf", values);

    return 0;
}

2024/1/23 17:01
加载中...