Solution
只要取出 个点，都可以说明这些点可以配对（从左到右，从右到左依次配对）。
所以，我们只需要以代价排一遍序，左边取 个数，再以坐标为关键字排序配对即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<bits/stdc++.h>
using namespace std;
struct Node{
int x,w,id;
}nd[200001];
vector<Node> ans;
bool cmp(Node a,Node b) { return a.w<b.w; }
bool cmp2(Node a,Node b) { return a.x<b.x; }
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m,sum=0;
cin>>n>>m;
for(int i=1;i<=m;i++) nd[i].id=i;
for(int i=1;i<=m;i++) cin>>nd[i].x>>nd[i].w;
sort(nd+1,nd+m+1,cmp);
ans.clear();
for(int i=1;i<=n*2;i++) sum+=nd[i].w,ans.push_back(nd[i]);
cout<<sum<<endl;
sort(ans.begin(),ans.end(),cmp2);
for(int i=0;i<ans.size()/2;i++) cout<<ans[i].id<<" "<<ans[ans.size()-i-1].id<<endl;
}
return 0;
}
|