题解：P17068 [ICPC 2017 Shenyang R] Defense of the Ancients

· · 题解

题意简述

双方各有若干单位，每个单位有生命值与攻击力。 存活单位会集火一个敌人，击杀后再选择下一个目标。 双方都采用最优击杀顺序，求最终胜负。

解题思路

先固定双方的击杀顺序。 对单位队累计受到的伤害量记为 x， 对防御塔队累计受到的伤害量记为 y。 再定义：

在游戏尚未结束时，双方造成伤害的速度分别等于当前总攻击力，因此：

\begin{aligned} \frac{\mathrm{d}x}{\mathrm{d}t} & =B(y) \\ \frac{\mathrm{d}y}{\mathrm{d}t} & =A(x) \end{aligned}

考虑两个势函数：

\begin{aligned} P(t) & =\int_0^{x(t)}A(s)\mathrm{d}s \\ Q(t) & =\int_0^{y(t)}B(s)\mathrm{d}s \end{aligned}

对时间求导可得：

\begin{aligned} P'(t) & =A(x)B(y) \\ Q'(t) & =B(y)A(x) \end{aligned}

又有 P(0)=Q(0)=0，所以游戏结束前始终满足 P(t)=Q(t)。

对于某一支队伍，设敌方依次击杀其第 1,2,\dots,n 个单位， 对应生命值和攻击力为 h_i,a_i。 在第 i 个单位承受伤害时， 该队仍有第 i 至第 n 个单位存活。 当整支队伍恰好被消灭时，其势函数达到：

F=\sum_{i=1}^{n}h_i\sum_{j=i}^{n}a_j

可以把 F 看成这支队伍的耐久阈值。 两边的势函数始终相等， 所以阈值较小的一方先被消灭；阈值相等时双方同时被消灭。

每支队伍决定的是对方的击杀顺序。 为了尽快消灭对方，应让对方的 F 尽量小。 考虑顺序中相邻的两个单位 x,y， 它们之后仍然存活的单位总攻击力记为 S。 先击杀 x 时，与这两者有关的贡献为：

h_x(a_x+a_y+S)+h_y(a_y+S)

先击杀 y 时，贡献为：

h_y(a_y+a_x+S)+h_x(a_x+S)

前者减去后者等于 h_xa_y-h_ya_x。 因此先击杀 x 不劣，当且仅当：

\frac{h_x}{a_x}\le\frac{h_y}{a_y}

由相邻交换法，按 h_i/a_i 递增就是使 F 最小的顺序。 比例相等时交换不改变答案。

代码把这个顺序反转，按 h_i/a_i 递减排列。 依次加入攻击力后，当前前缀攻击力正好等于原击杀顺序中的后缀攻击力， 于是可以直接累加 h_i 与前缀攻击力的乘积。 比较比例时使用交叉相乘，避免浮点误差。

攻击力总和能装入 64 位无符号整数， 但 F 的最大值会超过 64 位，所以乘积与答案使用 128 位无符号整数。 排序决定总时间复杂度为 O(n\log n+m\log m)，空间复杂度为 O(n+m)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ull=unsigned long long;
using u128=__uint128_t;
const int N=100005;
struct unit
{
    ull h,a;
};
unit a[N],b[N];
bool cmp(const unit &x,const unit &y)
{
    return (u128)x.h*y.a>(u128)y.h*x.a;
}
u128 calc(unit a[],int n)
{
    sort(a+1,a+n+1,cmp);
    ull sum=0;
    u128 res=0;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i].a;
        res+=(u128)a[i].h*sum;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>a[i].h;
        for(int i=1;i<=n;i++)cin>>a[i].a;
        for(int i=1;i<=m;i++)cin>>b[i].h;
        for(int i=1;i<=m;i++)cin>>b[i].a;
        u128 x=calc(a,n);
        u128 y=calc(b,m);
        if(x>y)cout<<"Units win";
        else if(x<y)cout<<"Towers win";
        else cout<<"Tie";
        cout<<'\n';
    }
    return 0;
}