codeforce #776 Weight of the System of Nested Segments

原题链接

思路

给定m个点要选2n个点使得所有点的权值和最小 可将所有点按照权值大小排序，从前往后选2n个点即可*

代码

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int position,weight,id;
};
void solve()
{
       int n,m;cin>>n>>m;vector<Node> p(m);for(int i=0;i<m;i++){
    cin>>p[i].position>>p[i].weight;p[i].id=i+1;}sort(p.begin(),p.end(),[](Node a,Node b){
    return a.weight<b.weight;});    //按照权值来排序int sum=0;for(int i=0;i<m;i++){
    if(i<2*n)sum+=p[i].weight;else p.pop_back();          //只需2n个点其余无用}cout<<sum<<endl;sort(p.begin(),p.end(),[](Node a,Node b){
    return a.position<b.position;});                        //将所选点按照位置排序for(int i=0;i<n;i++)cout<<p[i].id<<' '<<p[2*n-i-1].id<<endl;    //按照题目要求输出即可
}
int main()
{
    int T;cin>>T;while(T--){
    solve();}
}