唉，我太弱了，什么都不会，题也做不来。很明显这道题先要把不过河的人排除了，剩下的都是要过河的。当 k=1 k = 1 时，看看每个人的答案是多少：
显然，对于每个人，它对答案的贡献是两个端点到桥的距离之和。所以求一个中位数就好啦！（22 分 get，做了这么久 APIO 终于得分了 QAQ）
唉，我太弱了，什么都不会，连想题都想不出来。
显然，当我们确定了哪些人走第一座桥，哪些人走第二座桥后，就可以通过求中位数解决这个问题了。
由以上做法，我们可以大胆猜测：桥一定建在一个房子那里。因此我们可以 O(n2) O ( n 2 ) 枚举了。
唉，我太弱了，之前推导出来的是错的。
发现，桥离线段的中点越近越好：显然当不能直接过桥时中点离桥越远答案越大。所以我们按中点位置排序。现在问题从选一个集合变成了选一个分割点。
所以现在的问题是要求维护一个数据结构，支持插入一个数、删除一个数、查找第
k
k
大（中位数）、求比第 大小的数之和、求比第
k
k
<script type="math/tex" id="MathJax-Element-9">k</script> 大大的数之和。用权值线段树即可，你用 Splay 也行，Treap 也 OK，甚至你可以试试 vector。
结果我用的是对顶 set……
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
#define loop register int
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
}
const int maxn = int(1e5) + 5;
int k, n;
LL base;
struct Place
{
int a, b;
bool operator<(const Place& y) const
{
return a + b < y.a + y.b;
}
} places[maxn];
#define RunInstance(x) delete new x
struct cheat
{
int all[maxn * 2];
cheat()
{
for (int i = 1; i <= n; i++)
{
all[i - 1] = places[i].a;
all[i - 1 + n] = places[i].b;
}
std::nth_element(all, all + n, all + (n << 1));
int mid = all[n];
LL ans = 0;
for (loop i = 0, to = n << 1; i < to; i++)
ans += std::abs(all[i] - mid);
printOut(ans + base);
}
};
struct work
{
struct MultiSet : public std::multiset<int>
{
LL sum;
MultiSet() : sum() {}
void push(int t)
{
sum += t;
std::multiset<int>::insert(t);
}
void pop(int t)
{
sum -= t; // note
std::multiset<int>::erase(std::multiset<int>::find(t));
}
};
struct OppositeSet
{
MultiSet small, big;
void adjust()
{
if (!((small.size() + big.size()) & 1))
{
while (small.size() > big.size())
{
big.push(*small.rbegin());
small.pop(*small.rbegin());
}
while (small.size() < big.size())
{
small.push(*big.begin());
big.pop(*big.begin());
}
}
else
{
while (small.size() > big.size() + 1)
{
big.push(*small.rbegin());
small.pop(*small.rbegin());
}
while (small.size() < big.size() + 1)
{
small.push(*big.begin());
big.pop(*big.begin());
}
}
}
void push(int x)
{
if (!big.size() || x < *big.begin())
small.push(x);
else
big.push(x);
adjust();
}
void pop(int x)
{
if (big.size() && x >= *big.begin())
big.pop(x);
else
small.pop(x);
adjust();
}
} set1, set2;
static LL calc(const OppositeSet& set)
{
if (!set.small.size()) return 0;
LL mid = *set.small.rbegin();
return mid * set.small.size() - set.small.sum + set.big.sum - mid * set.big.size();
}
work()
{
LL INF;
memset(&INF, 0x3f, sizeof(INF));
std::sort(places + 1, places + 1 + n);
for (int i = 1; i <= n; i++)
{
set2.push(places[i].a);
set2.push(places[i].b);
}
LL ans = calc(set2);
for (int i = 1; i <= n; i++)
{
set1.push(places[i].a);
set1.push(places[i].b);
set2.pop(places[i].a);
set2.pop(places[i].b);
ans = std::min(ans, calc(set1) + calc(set2));
}
printOut(ans + base);
}
};
void run()
{
k = readIn();
n = readIn();
int valid = 0;
for (int i = 1; i <= n; i++)
{
char type[2][4];
scanf("%s", type[0]);
int p1 = readIn();
scanf("%s", type[1]);
int p2 = readIn();
if (type[0][0] == type[1][0])
base += std::abs(p1 - p2);
else
{
if (type[0][0] == 'B')
std::swap(p1, p2);
valid++;
places[valid].a = p1;
places[valid].b = p2;
}
}
n = valid;
base += n;
if (k == 1)
RunInstance(cheat);
else
RunInstance(work);
}
int main()
{
run();
return 0;
}