时间戳

首页 > 解决方案 > Kattis 惹恼了同事问题（自排序数据结构和最小堆）

c++ - Kattis 惹恼了同事问题（自排序数据结构和最小堆）

问题描述

好的，所以我正在尝试创建一个维护大量数据的数据结构，以便在编译时间限制内解决。https://open.kattis.com/problems/annoyedcoworkers

自从我在去年左右开始编码以来，我可能会不知所措，上周我刚刚学习了排序和向量，昨天才学习了堆数据结构。但我真的很想解决这个问题。

无论如何，我首先开始用选择排序解决这个问题......不用说它花了太长时间。然后我开始研究创建一个产生按顺序排列的值的堆数据结构，这将我带到了priority_queue 在尝试不同的方法大约 9 小时后，这是我最接近解决问题的方法。

有人对为什么在 25/27 测试用例之后我的代码返回错误答案有任何建议吗？

这是我的代码：

// C++ program to use priority_queue to implement Min Heap
// for user defined class
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;


// User defined class, coworker
class CoworkerT
{
private:
    int a;
    int d;
public:
    CoworkerT(int _a, int _d)
    {
        a = _a;
        d = _d;
    }
    int SimAddAD() const
    {
        int aD;
        aD = a + d;
        return aD;
    }

    int AddAD()
    {
        a = a + d;
        return a;
    }

    int getA() const {
        return a;
    }

    int getD() const {
        return d;
    }
};


// To compare two coworkers possible a value
class Min
{
public:
    int operator() (const CoworkerT& p1, const CoworkerT& p2)
    {
        return p1.SimAddAD() > p2.SimAddAD();
    }
};

//compare two a values between coworkers
class Max
{
public:
    int operator() (const CoworkerT& p1, const CoworkerT& p2)
    {
        return p1.getA() < p2.getA();
    }
};


int AskForA() {
    int a;
    cin >> a;
    return a;
}
int AskForD() {
    int d;
    cin >> d;
    return d;
}

priority_queue <CoworkerT, vector<CoworkerT>, Max >
PopulateMax(priority_queue <CoworkerT, vector<CoworkerT>, Max > max,
    priority_queue <CoworkerT, vector<CoworkerT>, Min > min) {


    while (min.empty() == false)
    {
        CoworkerT e = min.top();
        max.push(CoworkerT(e.getA(), e.getD()));
        min.pop();
    }


    return max;
}

// Driver code
int main()
{
    int h, c, i, a, d;

    cin >> h >> c;
    // Creates a Min heap of points (order by possible a +d combination )
    priority_queue <CoworkerT, vector<CoworkerT>, Min > pq;

    // Creates a Max heap of points (order by actual a value )
    priority_queue <CoworkerT, vector<CoworkerT>, Max > max;

    // Insert points into the min heap
    for (int i = 0; i < c; i++) {
        a = AskForA();
        d = AskForD();
        pq.push(CoworkerT(a, d));
    }
    i = 0;
    while (i < h) {
        CoworkerT e = pq.top();
        a = e.AddAD();
        d = e.getD();
        pq.pop();
        pq.push(CoworkerT(a, d));
        i++;
    }
    max = PopulateMax(max, pq);
    CoworkerT eMax = max.top();
    cout << eMax.getA() << endl;
    return 0;
}

标签： c++data-structurespriority-queueheap

解决方案

我只想说我最终使用了类似于使用堆的原始算法的东西。问题是我对 intI 的使用切换到了unsigned long long int~（尽管这可能有点矫枉过正？）它就像一个魅力。

// C++ program to use priority_queue to implement Min Heap
// for user defined class
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;


// User defined class, coworker
class CoworkerT {
private:
    unsigned long long int a;
    unsigned long long int d;
public:
    CoworkerT(unsigned long long int _a, unsigned long long int  _d){
        a = _a;
        d = _d;
    }
    unsigned long long int  SimAddAD() const{
        return  a + d;
    }
    unsigned long long int  AddAD(){
        return a + d;;
    }

    unsigned long long int getA() const {
        return a;
    }

    unsigned long long int getD() const {
        return d;
    }
};
//compare two coworkers possible a + d values
struct MinSort {
    bool operator()(const CoworkerT& p1, const CoworkerT& p2) const {
        return p1.SimAddAD() < p2.SimAddAD();
    }
};

//compare two coworkers possible a + d values ~for some reason heap lesser than or greater need to be reverse of operator for sort???
struct Min {
    bool operator()(const CoworkerT& p1, const CoworkerT& p2) const {
        return p1.SimAddAD() > p2.SimAddAD();
    }
};

//compare two a values between coworkers
struct MaxSort {
    bool operator()(const CoworkerT& p1, const CoworkerT& p2) const {
        return p1.getA() > p2.getA();
    }
};

void FindAndPrintMax(vector<CoworkerT>&  max) {
    sort(max.begin(), max.end(), MaxSort());
    CoworkerT minMax = max.front();
    cout << minMax.getA();
}
void InputCoworkersAD(vector<CoworkerT>& min, unsigned long long int& h, unsigned long long int& c) {
    int a, d, i;
    cin >> h >> c;
    // Insert a and d into the vector
    if (h <= 100000 && h >= 1 && c <= 100000 && c >= 1) {
        for (i = 0; i < c; i++) {
            cin >> a >> d;
            min.push_back(CoworkerT(a, d));
        }
    }
    make_heap(min.begin(), min.end(), Min());

}

void AskForHelp(vector<CoworkerT>& min, unsigned long long int h) {
    int i = 0;

    while (i < h) {
        push_heap(min.begin(), min.end(), Min());
        CoworkerT e = min.front();
        pop_heap(min.begin(), min.end(), Min());
        min.pop_back();
        min.push_back(CoworkerT(e.AddAD(), e.getD()));
        i++;

    }
}

// Driver code
int main()
{
    unsigned long long int  h, c;
    vector<CoworkerT> min;
    InputCoworkersAD(min, h, c);
    AskForHelp(min, h);
    FindAndPrintMax(min);

    return 0;
}

推荐阅读