0

我想在对数组上使用upper_bound，并且也使用比较对的第二个参数的比较器函数。请帮忙。

代码：

bool cmp(const pair<int,int> &p1, const pair<int,int> &p2)
{
    return p1.second<p2.second;
}

int subsets(pair<int,int> time[], int p)
{
    if(p == 0)  return 1;
    int j = upper_bound(time, time+p, time[p], cmp) - time;
}


编辑：我已经更正了返回类型，但我似乎没有得到我想要的输出。
我有一个命名时间数组，pair<int,int>其中包含开始和结束时间分别作为第一个和第二个参数，并根据结束时间以递增的方式排序。

目前我在索引 p。我想找到数组的最大索引（= j），这样time[j].second <= time[p].first.
例如。
time = { (1,5), (4,7) , (6, 12) } 如果 p = 2（基于 0 的索引），则 j 应为 = 0（如 5 <= 6 但 7 > 6）但上限给我 j = 2。

我怎样才能做到这一点？

4

2 回答 2

1

您的函数没有任何问题，cmp当您尝试存储std::upper_boundinto的返回值时引发了错误int j。

根据参考，std::upper_bound：

返回一个迭代器，该迭代器指向范围 [first, last) 中大于 value 的第一个元素，如果没有找到这样的元素，则返回 last。

因此，要获取找到的元素在time数组中的位置，您需要修改代码如下：

int j = upper_bound(time, time + p, time[p], cmp) - time;

或等效地，使用该std::distance功能。

另外，不要忘记检查这样的元素是否存在（即在这种情况下是否std::upper_bound返回）。time + p

于 2018-06-02T05:00:37.233 回答
0

以下代码完成了这项工作:)

bool compareit(int n, pair<int,int> &p)
{
    return p.second > n;
}

int subsets(pair<int,int> time[], int p)
{
    if(p == 0)  return 1;
    int j = upper_bound(time, time+p, time[p].first, compareit) - time;
}
于 2018-06-02T07:31:21.273 回答