Weight of the System of Nested Segments-Codeforces

投稿日：2022/04/10 更新日:2022/04/10

問題

数直線上に $m$ 個の点があります。 $i$ 番目の点は位置 $x_i$ に重みは $w_i$ です。すべての点は異なる位置にあります。

整数 $n$ が与えられるので以下の条件を満たす入れ子の区間を考えてください。

区間の端点は $m$ 個の与えられた点である。
区間の端点になっている $2n$ 個の点の重みの総和が最小である。

解法

まず、重みが小さい順に点を選びます。その後、選んだ点の中からまだペアになっていない最右端の点と最左端の点をペアとしていけば良いです。
最右端の点と最左端の点を選ぶことによって区間を入れ子にできます。

実装

#include <bits/stdc++.h>
using namespace std;

struct Point{
    int i, x, w;
};

void solve(){
    int n, m;
    cin >> n >> m;
    vector<Point> xw;
    for(int i = 0;i < m; ++i){
        Point p;
        cin >> p.x >> p.w;
        p.i = i + 1;
        xw.push_back(p);
    }

    sort(xw.begin(), xw.end(), [](Point a, Point b){return a.w < b.w;});

    vector<Point> select;
    for(int i = 0;i < 2*n; ++i){
        select.push_back(xw[i]);
    }

    sort(select.begin(), select.end(), [](Point a, Point b){return a.x < b.x;});

    long long sum = 0;
    for(Point p : select){
        sum += p.w;
    }

    cout << sum << endl;
    for(int i = 0;i < n; ++i){
        cout << select[i].i << " " << select[2*n-1 - i].i << endl;
    }
    cout << endl;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}