Weight of the System of Nested Segments

Weight of the System of Nested Segments

题目分析

贪心+结构体排序
由于输出按照输入的顺序，所以将num定义为输入顺序；
对结构体排序，将权值最小的放在前2n项，再将它们用坐标排序；
需要n个嵌套，所以前2*n一定符合条件；

代码

#include<iostream>
#include<algorithm>
using namespace std;
struct k
{
    int val;int num;int pos;
}ok[200001];
bool cmp(k x,k y)
{
    return x.val < y.val;
}
bool cmp1(k x, k y)
{
    return x.pos < y.pos;
}
int main()
{
    int n, m;int t;cin >> t;while (t--){
    int sum = 0;cin >> n >> m;for (int i = 1; i <= m; i++){
    cin >> ok[i].pos >> ok[i].val;ok[i].num = i;}sort(ok + 1, ok + m + 1, cmp);sort(ok + 1, ok + n * 2+1, cmp1);for (int i = 1; i <= 2 * n; i++)sum += ok[i].val;cout << sum << endl;for (int i = 1; i <= n; i++)cout << ok[i].num << " " << ok[2 * n - i + 1].num << endl;cout << endl;}return 0;
}