search

JianGuanTHU / UOJ_Offline

Offline test system for THUOOP
7 stars 0 forks source link

Proposal （第五次作业，多重排序） #22

Open yuguojia opened 2 years ago

yuguojia commented 2 years ago

考点

函数对象、std::function、lambda表达式、类模板

SubTask 1

很多时候排序仅仅靠一个关键字是不够的。例如考试排名，首先按总分降序排列；如果总分相同，再按照语文成绩降序排列；如果语文成绩也相同，再按照数学成绩降序排列……

现在我们来考虑一个具体的问题。给定n个2维点(x,y)，首先按点到原点的距离从小到大排序；如果两点距离相同，则按x坐标从小到大排序；如果仍相同，则按y坐标从小到大排序。

我们有point类已经写好：

class point {
public:
    int x, y;
    int dis() { return x*x + y*y; }
};

以及比较两个点到原点距离的函数、比较两点x/y坐标大小的函数：

auto discomp = [](point l, point r) { return l.dis() < r.dis(); };
auto xcomp = [](point l, point r) { return l.x < r.x; };
auto ycomp = [](point l, point r) { return l.y < r.y; };

你需要实现一个Compare类来完成这样的多重排序，就像这样：

vector<point> v;
// ...
Compare<point> comp = { discomp,xcomp,ycomp };
sort(v.begin(),v.end(),comp);

完整的main.cpp如下

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include "compare.h"
using namespace std;

class point {
public:
    int x, y;
    int dis() { return x*x + y*y; }
};

istream& operator>> (istream& in, point& p) {
    string s; int x, y;
    in >> s;
    sscanf(s.c_str(), "(%d,%d)", &x, &y);
    p.x = x, p.y = y;
    return in;
}

ostream& operator<< (ostream& out, const point& p) {
    out << "(" << p.x << "," << p.y << ")";
    return out;
}

int main()
{
    auto discomp = [](point x, point y) { return x.dis() < y.dis(); };
    auto xcomp = [](point x, point y) { return x.x < y.x; };
    auto ycomp = [](point x, point y) { return x.y < y.y; };

    Compare<point> comp = { discomp,xcomp,ycomp };

    int n;
    cin >> n;
    vector<point> v;

    while (n--) {
        point p;
        cin >> p;
        v.push_back(p);
    }

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

    for (auto p : v)
        cout << p << ' ';
    return 0;
}

你需要自己编写compare.h以实现上述功能。

SubTask 2

现在对于一个给定的表（每一列有列标题），你需要按用户指定的顺序进行多重排序。 表的内容都是int型。

输入样例：

4 4 3                                // 表4行4列（不含列标题）；多重排序有3个指令
Chinese math English total           // 列标题
 98  98 100 296
100  98  98 296
 98 100  98 296
100 100 100 300
total d                              // 首先按total列降序排列
Chinese d                            // 然后按Chinese列降序排列
math a                               // 最后按math列升序排列

输出样例：

Chinese math English total
100 100 100 300
100 98 98 296
98 98 100 296
98 100 98 296

main.cpp已写好，已经实现表的列标题和内容的读取，以及整个表的输出，你不能修改；你需要编写sort.cpp实现make_comp函数，从IO流中读入多重排序的指令，并返回一个Compare<vector<int>>作为sort函数的比较器。

main.cpp：

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include "compare.h"
using namespace std;

Compare<vector<int>> make_comp(vector<string>,int);

int main()
{
    int m, n, b;
    cin >> m >> n >> b;

    vector<vector<int>> v(m, vector<int>(n));  // 生成m行n列的vector

    vector<string> titles;
    for (int i = 0; i < n; i++) {
        string title;
        cin >> title;
        titles.push_back(title);
    }

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> v[i][j];

    sort(v.begin(), v.end(), make_comp(titles,b));

    for (auto s : titles)
        cout << s << ' ';
    cout << '\n';
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
            cout << v[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}
hzhwcmhf commented 2 years ago

整体可以。有几个问题：

  1. 两个subtask尽量用同一个背景，main函数差别太大比较难以理解。你可以说不同subtask是main.cpp里不同位置使用的功能。
  2. 如果一定要涉及initializer_list的话，麻烦在题目开头科普一下
yuguojia commented 2 years ago

SubTask 1

很多时候排序仅仅靠一个关键字是不够的。例如考试排名，首先按总分降序排列；如果总分相同，再按照语文成绩降序排列；如果语文成绩也相同，再按照数学成绩降序排列……

现在我们来考虑一个具体的问题。给定n个3维点(x,y,z)，按x坐标从小到大排序；如果x坐标相同，则按y坐标从小到大排序；如果仍相同，则按z坐标从小到大排序

我们有point类已经写好：

class point {
public:
    int x, y, z;
};

以及比较两点x/y坐标大小的函数：

auto xcomp = [](point l, point r) { return l.x < r.x; };
auto ycomp = [](point l, point r) { return l.y < r.y; };
auto zcomp = [](point l, point r) { return l.z < r.z; };

你需要实现一个Compare模板类来完成这样的多重排序，就像这样：

vector<point> v;
// ...
Compare<point> comp = { xcomp,ycomp,zcomp };
sort(v.begin(),v.end(),comp);

上面的代码，用花括号围起来的部分是一个std::initializer_list<std::function<bool(point,point)>>，其中就保存着这三个比较函数。这道题你不需要知道std::initializer_list的太多细节，你只需要知道std::list可以接受一个std::initializer_list的初始化，所以你可以在Compare类的构造函数中将std::initializer_list拷贝到std::list中。例如下面的代码：

std::initializer_list<int> initializer = {1,2,3};
std::list<int> l(initializer);

就可以将{1,2,3}拷贝给std::list l。

输入格式 第一行为一个整数n，表示总共有多少个点。 后n行，每行有3个用空格隔开的数字，分别代表点的x/y/z坐标

输出格式 输出n行，为排序后的点

输入样例 3 1 1 1 1 0 1 1 1 0

输出样例 1 0 1 1 1 0 1 1 1

完整的main.cpp如下

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include "compare.h"
using namespace std;

class point {
public:
    int x, y, z;
};

istream& operator>> (istream& in, point& p) {
    int x, y, z;
    in >> x >> y >> z;
    p.x = x, p.y = y, p.z = z;
    return in;
}

ostream& operator<< (ostream& out, const point& p) {
    out << p.x << " " << p.y << " " << p.z;
    return out;
}

int main()
{
    auto xcomp = [](point l, point r) { return l.x < r.x; };
    auto ycomp = [](point l, point r) { return l.y < r.y; };
    auto zcomp = [](point l, point r) { return l.z < r.z; };

    Compare<point> comp = { xcomp,ycomp,zcomp };

    int n;
    cin >> n;
    vector<point> v;

    while (n--) {
        point p;
        cin >> p;
        v.push_back(p);
    }

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

    for (auto p : v)
        cout << p << '\n';
    return 0;
}

你需要自己编写compare.h以实现上述功能。

SubTask 2

事实上，在SubTask 1中，我们完成了一个n行3列的表的一个多重排序：先按第一列升序，再按第二列升序，再按第三列升序。我们能否稍微拓展一些呢？

现在对于一个m行n列的表，你需要按用户指定的顺序进行多重排序。 表的内容都是int型。

输入格式 第一行为3个数字m,n,d，表示表格有m行n列，多重排序有d条指令 随后m行，每行n个整数，表示这个m行n列的表格 随后d行，每行开头是一个数字，表示要排序的列；随后是一个字母，如是a，代表这一列升序排列；如是b，代表这一列降序排列。

输入样例：

5 4 3                                // 表5行4列；多重排序有3个指令
1 2 3 4
0 2 3 4
1 2 4 4
1 2 3 3
1 2 2 5
1 d                              // 首先按第1列降序排列
3 d                            // 然后按第3列降序排列
4 a                               // 最后按第4列升序排列

输出样例：

1 2 4 4
1 2 3 3
1 2 3 4
1 2 2 5
0 2 3 4

main.cpp已写好，已经实现表的列标题和内容的读取，以及整个表的输出，你不能修改；你需要编写sort.cpp实现make_comp函数，从IO流中读入多重排序的指令，并返回一个Compare<vector<int>>作为sort函数的比较器。

main.cpp：

#include <vector>
#include <algorithm>
#include <iostream>
#include "compare.h"
using namespace std;

Compare<vector<int>> make_comp(int);

int main()
{
    int m, n, b;
    cin >> m >> n >> b;

    vector<vector<int>> v(m, vector<int>(n));  // 生成m行n列的vector

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> v[i][j];

    sort(v.begin(), v.end(), make_comp(b));

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
            cout << v[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}
hzhwcmhf commented 2 years ago

很多时候排序仅仅靠一个关键字是不够的。例如考试排名，首先按总分降序排列；如果总分相同，再按照语文成绩降序排列；如果语文成绩也相同，再按照数学成绩降序排列……

本题希望你能编写一个Compare函数对象，能够结合多个关键字进行排序。

首先我们来考虑一个具体的问题。给定n个3维点(x,y,z)，按x坐标从小到大排序；如果x坐标相同，则按y坐标从小到大排序；如果仍相同，则按z坐标从小到大排序。例如以下代码：

class point {
public:
    int x, y, z;
};
vector<point> v;
// insert some points into v ...
auto xcomp = [](point l, point r) { return l.x < r.x; };
auto ycomp = [](point l, point r) { return l.y < r.y; };
auto zcomp = [](point l, point r) { return l.z < r.z; };
Compare<point> comp = { xcomp,ycomp,zcomp };
sort(v.begin(),v.end(),comp);

其中xcomp, ycomp, zcomp 是lambda表达式，等价于一个函数来比较point的x、y、z坐标，你可以在这里查看lambda表达式的简要介绍（这里补充网址）。 Compare<point> comp = { xcomp,ycomp,zcomp };是使用一个std::initializer_list作为参数初始化Compare<point>对象。在这里，你不需要知道initializer_list的太多细节，你可以直接使用stl的容器（例如std::vector或std::list）作为构造函数的参数，编译器会自动进行转换。更多内容可以参考（这里补充网址）。

在上面的一段代码里，我们完成了一个n行3列的表的一个多重排序：先按第一列升序，再按第二列升序，再按第三列升序。我们能否稍微拓展一些呢？

现在对于一个m行n列的vector，你需要按用户指定的顺序进行多重排序。例如以下代码：

//这里只给一些简要代码

其中你需要编写make_comp函数，//后面给一些简要解释

本题分为两个Subtask，其中subtask1是对point的排序，subtask2是对表的排序

Subtask1

输入格式 第一行为一个整数n，表示总共有多少个点。 后n行，每行有3个用空格隔开的数字，分别代表点的x/y/z坐标

输出格式 输出n行，为排序后的点

输入样例 3 1 1 1 1 0 1 1 1 0

输出样例 1 0 1 1 1 0 1 1 1

增加一些对提交的要求

SubTask 2

输入格式 第一行为3个数字m,n,d，表示表格有m行n列，多重排序有d条指令 随后m行，每行n个整数，表示这个m行n列的表格 随后d行，每行开头是一个数字，表示要排序的列；随后是一个字母，如是a，代表这一列升序排列；如是b，代表这一列降序排列。

输入样例：

5 4 3                                // 表5行4列；多重排序有3个指令
1 2 3 4
0 2 3 4
1 2 4 4
1 2 3 3
1 2 2 5
1 d                              // 首先按第1列降序排列
3 d                            // 然后按第3列降序排列
4 a                               // 最后按第4列升序排列

输出样例：

1 2 4 4
1 2 3 3
1 2 3 4
1 2 2 5
0 2 3 4

main.cpp已写好，已经实现表的列标题和内容的读取，以及整个表的输出，你不能修改；你需要编写sort.cpp实现make_comp函数，从IO流中读入多重排序的指令，并返回一个Compare<vector<int>>作为sort函数的比较器。

  1. 题面大概按这个整理一下，有一个共同的描述，不要一开始就是两个subtask。上面是我大概改了下，有些部分需要补充。而且介绍时代码尽量精简吧，突出需要填写的部分，要不然两个task差得太远，都不知道联系的点是什么。
  2. point最好首字母大写
  3. 两个subtask的main使用不同的名字，比如main_subtask1.cpp main_subtask2.cpp，然后分发下去。两个应该共用提交同一个Compare.h就行吧？这个最后也要写清楚。
  4. 然后分数情况，数据范围都要写一下
yuguojia commented 2 years ago

1

很多时候排序仅仅靠一个关键字是不够的。例如考试排名，首先按总分降序排列；如果总分相同，再按照语文成绩降序排列；如果语文成绩也相同，再按照数学成绩降序排列……

本题希望你能编写一个Compare函数对象，能够结合多个关键字进行排序。

首先我们来考虑一个具体的问题。给定n个3维点(x,y,z)，按x坐标从小到大排序；如果x坐标相同，则按y坐标从小到大排序；如果仍相同，则按z坐标从小到大排序。例如以下代码：

class Point {
    public:
    int x, y, z;
};
vector<Point> v;
// insert some points into v ...
auto xcomp = [](Point l, Point r) { return l.x < r.x; };
auto ycomp = [](Point l, Point r) { return l.y < r.y; };
auto zcomp = [](Point l, Point r) { return l.z < r.z; };
Compare<Point> comp = { xcomp,ycomp,zcomp };
sort(v.begin(),v.end(),comp);

其中xcomp, ycomp, zcomp 是lambda表达式，等价于一个函数来比较point的x、y、z坐标，你可以在这里查看lambda表达式的简要介绍（稍后补充）。

Compare<point> comp = { xcomp,ycomp,zcomp };是使用一个std::initializer_list作为参数初始化Compare<point>对象。在这里，你不需要知道initializer_list的太多细节，你可以直接使用stl的容器（例如std::vector或std::list）作为构造函数的参数，编译器会自动进行转换。更多内容可以参考（稍后补充）。

2

在上面的一段代码里，我们完成了一个n行3列的表的一个多重排序：先按第一列升序，再按第二列升序，再按第三列升序。我们能否稍微拓展一些呢？

现在对于一个m行n列的表，你需要按用户指定的顺序进行多重排序（类似于Excel中的自定义排序） alt 为了方便排序顺序的指定，定义一个enum和一个struct如下：

enum order_type {ASCEND,DESCEND};  // ASCEND表示按升序排列，DESCEND表示按降序排列
struct sort_level {
    int column;      // 排序的是第几列（列编号从1开始）
    order_type order;     // 是升序还是降序
};

其中sort_level的column成员的编号从1开始。

这样我们可以通过一个std::list<sort_level>来指定多重排序的顺序，例如：

std::list<sort_level> sortlevels = { {1,DESCEND},   // 首先按第1列降序排列
                                     {3,DESCEND},   // 然后按第3列降序排列
                                     {4,ASCEND} };  // 最后按第4列升序排列

现在，对于一个m行n列的vector<vector<int>>，你需要编写一个make_comp函数作为std::sort的比较器，按照指定的顺序进行多重排序，例如下面的代码：

vector<vector<int>> v;
// 定义一个5行4列的vector
v={{1,2,3,4},
   {0,2,3,4},
   {1,2,4,4},
   {1,2,3,3},
   {1,2,2,5}};
std::sort(v.begin(), v.end(), make_comp(sortlevels));  // 用上面的sortlevels进行多重排序
/* 此时v的值应该为
{{1,2,4,4},
 {1,2,3,3},
 {1,2,3,4},
 {1,2,2,5},
 {0,2,3,4}}
*/

注意：你的make_comp函数应该通过前面编写的Compare类来实现。具体来说，你的make_comp函数应该返回一个Compare<vector<int>>作为std::sort的比较器， 也即，make_comp的声明已经规定为：

Compare<vector<int>> make_comp(std::list<sort_level>);

本题分为两个Subtask，其中subtask1是对point的排序，subtask2是对表的排序

Subtask1

通过文件中main_subtask1.cpp进行测试。你不应修改main_subtask1.cpp的内容；你应该编写compare.h完成题目要求。OJ编译时通过命令g++ main_subtask1.cpp进行编译

输入格式 第一行为一个整数n，表示总共有多少个点。 后n行，每行有3个用空格隔开的数字，分别代表点的x/y/z坐标

输出格式 输出n行，为排序后的点

输入样例 3 1 1 1 1 0 1 1 1 0

输出样例 1 0 1 1 1 0 1 1 1

数据范围 1≤n≤100，x、y、z坐标在int范围内

SubTask 2

通过文件中main_subtask2.cpp进行测试。你不应修改main_subtask2.cpp的内容；你应该编写sort.cpp完成题目要求。编译时通过命令g++ main_subtask2.cpp sort.cpp进行编译

输入格式 第一行为3个数字m,n,d，表示表格有m行n列，多重排序有d条指令 随后m行，每行n个整数，表示这个m行n列的表格 随后d行，每行开头是一个数字k，表示要排序的是第k列（列编号从1开始）；随后是一个字母，如是a，代表这一列升序排列；如是d，代表这一列降序排列。

输入样例：

5 4 3 // 表5行4列；多重排序有3个指令 1 2 3 4 0 2 3 4 1 2 4 4 1 2 3 3 1 2 2 5 1 d // 首先按第1列降序排列 3 d // 然后按第3列降序排列 4 a // 最后按第4列升序排列 输出样例：

1 2 4 4 1 2 3 3 1 2 3 4 1 2 2 5 0 2 3 4

数据范围 1≤m,n≤100，表格数字在int范围内 1≤d,k≤n 数据保证k不重复

提交方式

你需要提交两个文件：compare.h和sort.cpp。（就用类似于http://115.182.62.169:8000/problem/89的提交界面）

Subtask 1只会用到compare.h，并不会用到sort.cpp。Subtask 2会同时用到compare.h和sort.cpp。

hzhwcmhf commented 2 years ago

好的，没有问题。请将完整题面、数据（包括数据生成文件）、judger和答案程序，自行测试通过。完成之后发到邮箱 huangfei382@163.com。对于编写judger有问题可在小教员群（或找助教）讨论。