查询大于 X 的值，同时具有其他条件

Question

我有一对[x;y]，其中x是唯一的，y可以是重复的(整数)。

这里有一个问题:

给定一对[x;y]，找出新的一对[k;m]，使得:

• 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 %drn", parent, employees[index].sub_ordinates);
        }
    }
    return 0;
}

工资=x，身高=y

Answer 1

我将首先消除m<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; });
}