2

给定n二维空间中的点，按升序对所有点进行排序。

(x1,y1) > (x2,y2) if and only if (x1>x2) or (x1==x2 && y1<y2)

输入规格：

第一行包含一个整数t，即测试用例的数量。然后对于每个测试用例，第一行包含一个整数n，即点数。然后接下来的n行包含两个整数xi，yi 代表点。

输出规格：

对于每个测试用例，打印点的排序顺序。输入约束：

1 <= t <= 10
1 <= n <= 100000
- 10 ^ 9 <= co - ordinates <= 10 ^ 9

注意：严格的时间限制。更喜欢scanf/ printf/BufferedReader而不是cin/ cout/ Scanner。

样本输入：

1
5
3 4
-1 2
5 -3
3 3
-1 -2

样本输出：

-1 2
-1 -2
3 4
3 3
5 -3

我声明了 a ，现在如果键相等set，我想按降序（值）排序。这是我的代码：

int main() 
{
    int n, i, hold = 0;
    set<pair<int, int>>s;
    int x, y, t;
    set<pair<int, int>>::iterator it;

    SF(t)
        while (t--)
        {

            SF(n) while (n--) {
                SF(x) SF(y)
                    s.insert({ x,y });
            }

            for (it = s.begin(); it != s.end(); it++) {
                PF(it->first) printf(" "); PF(it->second); printf("\n");
            }
            s.clear();
        }
    return 0;
}

我的输出

-1 -2
-1 2
3 3
3 4
5 -3

如果键相同，我希望键值按降序排序。

4

3 回答 3

1

std::set默认情况下用作std::less默认比较器，用于比较插入它的元素。

在你的情况下，你有std::pair<int,int>你的元素类型，因此std::set使用标准中定义的默认值operator<std::pair，因此你没有得到你想要的结果。

为了实现您的自定义样式比较，您需要提供自定义比较器

template<
    class Key,
    class Compare = std::less<Key>,
 //                 ^^^^^^^^^^^^^^^ --> instead of this
    class Allocator = std::allocator<Key>
> class set;

应该满足compare的要求。从 C++11 开始，您还可以为此使用 lambda 函数：

以下是示例代码：（参见在线）

#include <iostream>
#include <set>
using  pairs = std::pair<int, int>;

int main()
{
    // custom compare
    const auto compare = [](const pairs &lhs, const pairs &rhs) 
    {
        return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second > rhs.second);
    };

    std::set<pairs, decltype(compare)> mySet(compare);

    mySet.emplace(3, 4);
    mySet.emplace(-1, 2);
    mySet.emplace(5, -3);
    mySet.emplace(3, 3);
    mySet.emplace(-1, -2);

    for (const auto& it : mySet)
        std::cout << it.first << " " << it.second << std::endl;
}

输出：

-1 2
-1 -2
3 4
3 3
5 -3
于 2019-07-15T12:23:37.290 回答
0

正如Jejo和其他人所回答的那样，您可以创建一个自定义比较器来指定您希望如何对您的点进行排序：

// custom compare
const auto compare = [](const pairs &lhs, const pairs &rhs) 
{
    return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second > rhs.second);
};

set<pair<int, int>, decltype(compare)> mySet(compare);

但是，如果您关心性能，您可能会发现使用 std::vector 和调用 std::sort 比 std::set/insert 替代方案快得多：

#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
    int n, i, hold = 0;
    vector<pair<int, int>> v;
    int x, y, t;

    SF(t)
        while (t--)
        {

            SF(n) 
            v.reserve(n);
            while (n--) {
                SF(x) SF(y)
                    v.emplace_back( x,y );
            }

            // custom comparitor
            const auto comp = [](const pairs &lhs, const pairs &rhs) 
            {
                return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second > rhs.second);
            };

            sort(v.begin(), v.end(), comp);

            for (const auto &p : v) {
                PF(p.first) printf(" "); PF(p.second); printf("\n");
            }
            v.clear();
        }
    return 0;
}

插入集合比插入向量然后排序慢的几个原因：

  1. std::set 实现涉及二叉树，通常是红黑树。有关详细信息，请参见此处。
  2. 迭代 std::set 中的元素范围要慢得多

请注意，这两种方法都需要 n 个分配，并且需要 nlog(n) 操作的顺序来进行插入 + 排序。

于 2019-07-15T14:44:34.597 回答
0

Set 默认情况下不会按照您想要的方式排序，因此您必须提供自己的比较功能。

struct MyComp
{
    bool operator()(const pair<int,int>& x, const pair<int,int>& y) const
    {
        return x.first < y.first || (x.first == y.first && x.second > y.second);
    }
};

set<pair<int,int>, MyComp> s;
于 2019-07-15T12:03:29.863 回答