1

ベクトル配列が次のルールでソートされていると仮定します。 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 );

したがって、コンパレーターを 4 番目の引数として渡すことができます。

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 に答える