Lonely Mountain Dungeons
算法本质
思维、数学、三分
题目大意
给定整数b x，有n种士兵，c[]表示每种士兵的数目。
玩家需要将所有士兵分成k支队伍：（k由玩家指定）
- 分成
k支队伍花费(k-1)*x - 若某2个士兵属于同兵种且不在同一支队伍，则收益
b
输出最大收益。
思路推演
首先想到的就是，士兵如何分队才能收益最大。
显然每种士兵之间互不打扰，然后就是没有任意同种士兵同一队伍，这肯定可以收益最大，但是同理我们需要付出更多的成本。但是这是一种思考方式，我们可以假设最初得到所有士兵的收益，若有同种士兵同队就扣去收益，这样计算显然更方便。
退而求其次，我们考虑对于一种士兵，有a个分配到k个队伍中。
隐约觉得平摊分是最合理的，我们可以来证明。
证：若存在a个同种士兵面对k支队伍，尽可能平摊分配是最优解。
平摊分配的意思是：
a%k 支队伍有 a/k+1 人
k-a%k 支队伍有 a/k 人
我们使用反证法：
对于任意一种非平摊分配法，都可以视作在平摊仅执行任意次以下操作：
* 选择2支队伍，其人数分别是a b，保证a>=b，将其人数更改为a+1 b-1
接下来我们证明，执行这个操作会导致收益降低或不变
对于任意一支有c同种人数的队伍，其收益会降低：f(c)=c(c-1)/2
所以实际上就是证明 f(a)+f(b) <= f(a+1)+f(b-1)
自行计算即可，实际上最后发现是必定小于的，没有等于情况我们可以得到公式：
- $f(x)=\frac{x*(x-1)}{2}$
- $sum = \sum_{i=1}^nf(c_i)*b$
- $cost(k) = (k-1)*x + b*( (k-c_i\%k)*f(c_i/k) + (c_i\%k)*(c_i/k+1) )$
- $ans(k) = sum - cost(k)$
注意公式中的除法表示向下整除
所以我们实际上是需要找到一个k来最小化ans。
其中sum的值是固定的，观察cost(k)，这个函数由2部分组成，一部分是递增的线性函数，另一部分是递减双曲线函数的平方。
显然这可以使用三分搞定。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
int f(int x)
{
if (x<=0) return 0;
return x*(x-1)/2;
}
int g(int k, int b, int x) // 注意这个计算的是负收益
{
int res = (k-1)*x;
for (int i=1; i<=n; i++)
res += b*( (k-a[i]%k)*f(a[i]/k) + (a[i]%k)*f(a[i]/k+1) );
return res;
}
int tri_search(int l,int r, int b, int x)
{
// 求凹函数的极小值
int f1, f2;
while(l < r) {
int lp = l + (r - l) / 3;
int rp = r - (r - l) / 3;
f1 = g(lp, b, x), f2 = g(rp, b, x);
if(f1 <= f2)
r = rp - 1;
else
l = lp + 1;
}
//查找的是极小值
return min(f1,f2);
//查找的是极小值对应的下标
return f1<f2?l:r;
}
inline void solve()
{
int b, x;
cin>>n>>b>>x;
for (int i=1; i<=n; i++) cin>>a[i];
sort(a+1, a+1+n);
int cost = tri_search(1, a[n], b, x);
int ans=0;
for (int i=1; i<=n; i++)
ans += f(a[i])*b;
ans -= cost;
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)