c++ - 查询大于 X 的值，同时具有另一个条件

Question

我有一对 [x;y] 的列表，其中 x 是唯一的，y 可以是重复的（整数）。

这里有一个问题：

给定一对 [x;y]，找到新的对 [k;m]，这样：

• k > x
• m >= y
• k - x 被最小化。

现在，我用这个逻辑解决了这个问题；我按 x 对对进行排序，然后在其上启动朴素的 O(n^2) 算法。它似乎工作正常，只是它太慢了。

我能做得更好吗？
我试图解决的实际问题在这里：http ://www.spoj.com/problems/VBOSS/ 和我当前的代码：

#include <stdio.h>
#include <utility>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

struct employee
{
    int id;
    int salary;
    int height;

    int parent_index;
    int sub_ordinates;

    int cur;
    bool important;

    bool operator < (const employee& e) const
    {
        if(height == e.height)
            return salary > e.salary;

        return (height > e.height);
    }
};

// problem states explictly that no two employees
// have same salary.
struct salary_predicate
{
    inline bool operator() (const employee& struct1, const employee& struct2)
    {
        return (struct1.salary > struct2.salary);
    }
};

const int MAX_EMPLOYEES = 30000;
const int MAX_QUERIES = 200;

employee employees[MAX_EMPLOYEES];
int queries[MAX_QUERIES];

int main()
{

    int test_cases;

    scanf("%d", &test_cases);

    while(test_cases--)
    {
        int employeeCount, queryCount;
        scanf("%d %d", &employeeCount, &queryCount);


        int i = 0;
        int j = 0;
        while(i < employeeCount)
        {
            employees[i].parent_index = -1;
            employees[i].sub_ordinates = 0;
            employees[i].cur = i;
            employees[i].important = false;

            scanf("%d %d %d", &employees[i].id, &employees[i].salary, &employees[i].height);
            i++;
        }

        map<int, int> mapper;
        while(j < queryCount)
        {
            scanf("%d", &queries[j]);
            mapper.insert(pair<int, int>(queries[j], -1));
            j++;
        }

        // now step1; sort employees structure
        // based on SALARY!!
        sort(employees, employees + employeeCount, salary_predicate());


        for(int k = 0; k < employeeCount; k++)
        {
            employees[k].cur = k;

            if(mapper.find(employees[k].id) != mapper.end())
            {
                mapper[employees[k].id] = k;
                employees[k].important = true;
            }
        }


        int found = 0;
        for(int l = employeeCount - 1; l >= 0; l--)
        {
            int gef = l - 1;

            // check out information about previous worker,
            // he might give us some valuable information!
            // with his help, we know if we can skip some shit :)
            if(l + 1 < employeeCount && employees[l + 1].parent_index != -1)
            {
                // if previous employee is smaller than our current employee
                // then we can skip some people, becase we know that answer cant be
                // smalle than that :)
                if(employees[l + 1].height <= employees[l].height)
                    gef = employees[l + 1].parent_index - 1;
            }

            // find boss!
            for(int b = gef; b >= 0; b--)
            {
                if(employees[b].height >= employees[l].height)
                {
                    employees[l].parent_index = b;
                    employees[b].sub_ordinates += employees[l].sub_ordinates + 1;
                    break;
                }
            }

            // this bit makes sure if we have processed all necessay things, 
            // then we can basically stop our work.
            if(employees[l].important) found++;
            if(found == mapper.size()) break;
        }

        // time to print it out.
        for(int b = 0; b < queryCount; b++)
        {
            int id = queries[b];
            int index = mapper[id];

            int parent_index = employees[index].parent_index;
            int parent = parent_index < 0 ? 0 : employees[parent_index].id;

            printf("%d %d\r\n", parent, employees[index].sub_ordinates);
        }
    }

    return 0;
}

薪水=x，身高=y。

Answer 1

我将首先消除所有记录 wherem<y或k<=x。然后从k剩下的内容中找到具有最小值的项目。这两者都应该是线性的，因此您的整体复杂性也应该是线性的。

struct p { 
    int k, m;
};

p find_item(p xy, std::vector<p> &values) { 
    auto end = std::partition(values.begin(), values.end(),
        [xy](p const &v) { return xy.k < v.k || xy.m >= v.m; });
    return *std::min_element(values.begin(), end, 
        [](p const &a, p const &b) { return a.k < b.k; });
}