比较简单的套路题。
我们能决定的是组与组之间的顺序，以及每个人从前面登船还是从后面登船。也就是说，我们要找到一个最优的，这
个组的排列，而每个元素的贡献只与其前面的元素有关。
不难想到设 表示
的组已经登船的最小期望。考虑新加一个组 ，令 。 表示在第
组前登船的组集合为 时 的贡献。
考虑如何计算 。事实上，第
组中每个乘客对期望的贡献独立，可单独计算最后再加起来。我们先假设所有乘客都走前面上船，此时一个乘客
的贡献又可拆分为：“属于 中的组的在 之前的乘客数” 与 ”在第 组中的在
之前的乘客数的期望”之和。前者是确定的，好算，主要来看后者。
设 之前一共有 个属于第 组的座位，注意 是不随第 组内部登船顺序而改变的定值。那么，这
个乘客中，有 个在 之前上船的概率，其实就是在一个长度为
的随机均匀生成的排列中， 排在第 位的概率。容易发现这个概率不随 而变化，就是 。所以，在 之前的同组乘客数的期望就是 。
上文的分析基于乘客
走前面上船，实际上这个人走后面上船的贡献也可类似计算，两者取 之后加入 即可。
这里给出计算
的暴力代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| db Calc(int S, int x) {
db ans = 0;
int s1 = 0, s2 = 0;
int n1 = 0, n2 = 0;
for (int i = 1; i <= n; i++)
s1 += (S >> a[i]) & 1, s2 += a[i] == x;
for (int i = 1; i <= n; i++) {
if (a[i] == x)
ans += min(n1 + n2 / 2.0, (s1 - n1) + (s2 - n2 - 1) / 2.0);
n1 += (S >> a[i]) & 1;
n2 += a[i] == x;
}
return ans;
}
|
直接 计算 可以得到一个 的做法，拿到 分的高分。
优化
的计算也很简单，注意到第
组中，走前门上船的一定是一段前缀，反之亦然，所以可以二分出那个分界点，在分界点前的都走前面，分界点后的都走后面，贡献用前缀和统计一下即可。时间复杂度
。可以通过此题。
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5,M = 16,Sz = 1 << 15;
template<typename T> inline bool ckmin(T &x,const T &y) { return (x > y) && (x = y,true);}
typedef double db;
typedef long long ll;
int n,m;
int a[N],id[N];
db f[Sz];
vector<int> Pos[N];
vector<ll> A[M][M],Sum[M][M];
db Calc(int S,int x) {
if(!Pos[x].size()) return 0;
auto calc1 = [&](const int &t) {
assert(t >= 0);
db res = t / 2.0;
for(int i = 0;i < m;i++)
if((S >> i) & 1) res += A[i][x][t];
return res;
};
auto calc2 = [&](const int &t) {
assert(t >= 0);
db res = ((int)Pos[x].size() - t - 1) / 2.0;
for(int i = 0;i < m;i++)
if((S >> i) & 1) res += (int)Pos[i].size() - A[i][x][t];
return res;
};
int lef = -1,rig = (int)Pos[x].size() - 1;
while(lef < rig) {
int mid = lef + rig + 1 >> 1;
if(calc1(mid) <= calc2(mid)) lef = mid;
else rig = mid - 1;
}
int siz = Pos[x].size();
db c1 = 1ll * lef * (lef + 1) / 4.0;
if(lef >= 0) for(int i = 0;i < m;i++) if((S >> i) & 1) c1 += Sum[i][x][lef];
db c2 = 1ll * (siz - 1 - lef) * (siz - 2 - lef) / 4.0;
for(int i = 0;i < m;i++) if((S >> i) & 1) c2 += 1ll * (siz - 1 - lef) * Pos[i].size() - (Sum[i][x].back() - (lef >= 0 ? Sum[i][x][lef] : 0));
return c1 + c2;
}
int main() {
string str;
cin >> str;
n = str.size();
for(int i = 0;i < n;i++)
a[i + 1] = str[i] - 'A',m = max(m,a[i + 1] + 1);
for(int i = 1;i <= n;i++) {
id[i] = Pos[a[i]].size();
Pos[a[i]].push_back(i);
}
for(int i = 0;i < m;i++) {
int cnt = 0;
for(int j = 1;j <= n;j++)
if(a[j] == i) ++cnt;
else A[i][a[j]].push_back(cnt);
for(int j = 0;j < m;j++)
if(i != j && Pos[j].size()) {
Sum[i][j].resize(Pos[j].size());
Sum[i][j][0] = A[i][j][0];
for(int k = 1;k < Pos[j].size();k++)
Sum[i][j][k] = Sum[i][j][k - 1] + A[i][j][k];
}
}
for(int i = 0;i < (1 << m);i++) f[i] = 1e18;
f[0] = 0;
for(int S = 0;S < (1 << m);++S)
for(int i = 0;i < m;i++)
if((~S >> i) & 1)
ckmin(f[S ^ (1 << i)],f[S] + Calc(S,i));
printf("%.3lf\n",f[(1 << m) - 1]);
return 0;
}
|