SP726 PRO - Promotion 题解

· · 题解

本题因数据范围较大，暴力 sort 无法通过，必须探索其他的做法。

因为本题需要同时维护单个序列中的最大值和最小值，所以我们可以很自然地想到使用 multiset。

multiset 是 STL 库里的“多重集合”，集合内的元素总是单调递增或单调递减，可以同时查询或删除最大值和最小值，并且能存储重复元素。

我们首先定义：

multiset<int> s;

具体地，s.begin() 是指向 multiset 中第一个元素的指针，prev(s.end()) 是指向最后一个元素的指针。可以通过 * 来获取其所指的元素的值，用 erase 函数来删除它们。

到这个时候，本题就变得十分容易。

放代码：

#include<bits/stdc++.h>
#define int long long // 本题大坑点，不开 long long 见祖宗
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n,c=0; cin>>n;
  multiset<int> s;
  for(int i=1;i<=n;i++){
    int k; cin>>k;
    for(int j=1;j<=k;j++){
      int x; cin>>x,s.emplace(x);
    }
    c+=*prev(s.end())-*s.begin(); // 答案加上最大的减去最小的
    s.erase(prev(s.end())),s.erase(s.begin()); // 删除头尾指针
  }
  cout<<c<<endl;
  return 0;
}