1

假设向量数组按以下规则排序：- A[i] > A[j] 对于 A[i] (a,b) 中的所有对和 A[j] a>c 中的所有对 (c,d) 和b>d。假设输入数组已排序。现在给定一个上述类型的数组，

A[0] = (0,1)
A[1] = (4,3), (2,5)
A[2] = (12,4), (10, 6)
...

现在您将一对作为输入，如何使用内置的 lower_bound 函数找到 lower_bound。我写了一个代码，但它给了我一些错误。我错过了什么？

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> mypair;
vector <mypair> A[100008];
mypair B;
bool operator < (const mypair &a1, const mypair &a2){
    return (a1.first < a2.first && a1.second < a2.second);
}
bool operator < (const vector<mypair> &a1, const mypair &a2){
        for(int i = 0; i< a1.size();i++){
            if (a1[i] < a2) 
                return true;
        }   
        return false;
}
bool operator < (const mypair &a1, const vector<mypair> &a2){
        for(int i = 0; i< a2.size();i++){
            if(a1 < a2[i])
                return true;
        }   
        return false;
}
int main()
{
    int N,x,y;
    scanf("%d",&N);
    int cnt = 0;
    for(int i=0;i<N;i++){
        scanf("%d %d",&x,&y);
        B = make_pair(x,y);
        // consider A as filled up as stated
        x = lower_bound(A,A+N,B) - A;
    }   
    return 0;
}
4

1 回答 1

5

函数lower_bound也为 4 个参数重载：

template<class FI, class T, class Comp>
FI lower_bound( FI first, FI last, const T& value, Comp comp );

因此，您可以将比较器作为第四个参数传递：

bool cmp(const vector<mypair> &a1, const mypair &a2){
    for(int i = 0; i< a1.size();i++){
        if (a1[i] < a2)
            return true;
    }
    return false;
}

// ...

x = lower_bound(A,A+N,B, cmp) - A;
于 2013-06-07T05:40:37.057 回答