为什么用优先队列会在test1 wa?
查看原帖
为什么用优先队列会在test1 wa?
817526
PhiliaTheCat楼主2023/9/14 17:52

rt,题意并没有要求保持相对顺序,因此相同接水时长的人之间自由换位应该是被允许的。

test1(也就是样例)的判定对相对顺序有要求,显然这不对劲。

如果有啥我没看到的要求,请大佬轻喷

#include <iostream>
#include <queue>
#include <iomanip>

using namespace std;

struct student
{
    int no, t;
};

void solve(priority_queue<student, vector<student>, greater<student>> &q);
inline bool operator >(const student &lhs, const student &rhs);

int main()
{
    int n;
    cin >> n;
    priority_queue<student, vector<student>, greater<student>> q;
    for (int i = 0; i < n; i += 1)
    {
        student temp;
        cin >> temp.t;
        temp.no = i + 1;
        q.push(temp);
    }
    solve(q);
    return 0;
}

void solve(priority_queue<student, vector<student>, greater<student>> &q)
{
    long long wait = 0;
    long long sum = 0;
    int i = 0;
    while (!q.empty())
    {
        sum += wait;
        cout << q.top().no << ' ';
        wait += q.top().t;
        q.pop();
        i += 1;
    }
    cout << endl;
    cout << fixed << setprecision(2) << double(sum) / i << endl;
    return;
}

bool operator >(const student &lhs, const student &rhs)
{
    return lhs.t > rhs.t;
}
2023/9/14 17:52
加载中...