一种似乎更快抽象的解法？
正文
看这道题，给定序列 \(l,r,c\)，要求重构 \(l,r,c\) 使得 \(\sum_{i=1}^n(r_i-l_i) \times c_i\) 最小。
首先可以想到的就是尽量让小的 \(r_i-l_i\) 乘上大的 \(c_i\)。这样子看来 \(c_i\) 几乎不需要更多的处理，仅需从小到大（或从大到小）排个序。
来看如何求出优秀的 \(r_i-l_i\)。
对于每一个 \(r_i-l_i\)，要使它们的差最小，最好的方法自然是使这两个数尽可能地相近并且 \(l_i<r_i\) 仍成立。因为题目中保证了初始序列的 \(l\) 与 \(r\) 满足 \(l_i<r_i\)。所以不存在构造不出满足目标的 \(l,r\) 序列。
假设已经找出了 \(n\) 个最优的 \(r_i-l_i\)，分别是 \(rl_1,rl_2 \sim rl_n\)。将它们展开后再合并会发现，无论 \(rl_i\) 的具体值是什么，始终会满足:
\[\sum _{i=1}^n rl_i=\sum_{j=1}^n r_j - \sum _{k=1}^n l_k \]说明在保证 \(rl\) 的选择最优的情况下，不管怎么排列并不会影响最终结果。这应该是显而易见的。
贪心的考虑一下，对于每个 \(r_i\)，找到比它小的最大的 \(l_j\) 匹配，得到的 \(rl\) 即是最小。若有多个 \(r\) 匹配同一个 \(l\)。则让最小的 \(r\) 匹配（能小则小）。
下面内容过于抽象所以请移步其它题解。
由于最近再练平衡树，练得脑子有点抽，诶？\(l_i,r_i\) 互不相同。比 \(r_i\) 小的最大值？于是自然而然地用到了三棵平衡树，来维护上面的 \(r,l\) 以及 \(rl\)。并且自己又非常懒惰，所以使用了 pb_ds。
头文件：
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>//平衡树
using namespace __gnu_pbds;
定义：
tree<ll , null_type , std::less<ll> , rb_tree_tag , tree_order_statistics_node_update> L , R;
tree<pair<ll , ll> , null_type , std::less<pair<ll , ll>> , rb_tree_tag , tree_order_statistics_node_update> RL;
在代码中用了如下操作：
-
insert插入一个数。代码内使用L.insert(l)。 -
erase擦除一个数或迭代器。代码内使用L.erase(nl)。 -
lower_bound返回指向首个不小于给定键的元素的迭代器。代码内使用ll nl = *(--L.lower_bound(nr));（注：自减操作是为了找到比 \(nr\) 小的最大值）。 -
order_of_key(x)返回 \(x\) 以比较的排名。代码内使用ll order = RL.order_of_key({rl , 0});。 -
find_by_order(x)返回的排名 \(x\) 所对应元素的迭代器。代码内使用ll rl = RL.find_by_order(0) -> first;。
当然，功能多多，码量远小于手写平衡树只是比赛时没什么用。
最后代码复杂度 \(O(Tn \log n)\)，勉强能看。
PS：魔怔人平衡树学傻了。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#define ll long long
#define fr(i , a , b) for(ll i = a ; i <= b ; ++i)
#define fo(i , a , b) for(ll i = a ; i >= b ; --i)
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>//平衡树
using namespace __gnu_pbds;
using namespace std;
tree<ll , null_type , std::less<ll> , rb_tree_tag , tree_order_statistics_node_update> L , R;
tree<pair<ll , ll> , null_type , std::less<pair<ll , ll>> , rb_tree_tag , tree_order_statistics_node_update> RL;
ll T , n , l , r , c[200005];
inline bool cmp(ll x , ll y)
{
return x > y;
}
ll sum;
signed main()
{
// freopen("in.in" , "r" , stdin);
// freopen("out.out" , "w" , stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
while(T--)
{
ll idx = 0;
cin >> n;
fr(i , 1 , n)
{
cin >> l;
L.insert(l);
}
fr(i , 1 , n)
{
cin >> r;
R.insert(r);
}
fr(i , 1 , n)
{
cin >> c[i];
}
fr(i , 1 , n)
{
ll nr = *(R.find_by_order(0));
ll nl = *(--L.lower_bound(nr));
RL.insert({nr - nl , ++idx});
L.erase(nl);
R.erase(nr);
}
sort(c + 1 , c + n + 1 , cmp);
sum = 0;
fr(i , 1 , n)
{
ll rl = RL.find_by_order(0) -> first;
sum += rl * c[i];
ll order = RL.order_of_key({rl , 0});
RL.erase(RL.find_by_order(order));
}
cout << sum << '\n';
}
return 0;
}