题解：ABC368C Triple Attack

前言

最难的 C。我的思路也很另类。

Stop learning other useless algorithms,go to solve problems,and learn how to use binary search. by Um_nik.

翻译

现在，有 \(N\) 个敌人的按顺序排成一行，记他们的生命值为：\(a_1,a_2,\dots,a_N\)，你有一个初始为 \(0\) 的量 \(T\)。

不断进行如下操作：

记目前最前面的敌人生命值为 \(a_i\)，满足 \(\forall j\in [1,i),a_j<1\)。

• 若 \(T\equiv 0 (\bmod\ 3)\)，让 \(a_i\) 减 \(3\)。
• 否则，让 \(a_i\) 减 \(1\)。

求让所有敌人生命值不大于 \(0\) 的最小操作次数。

思路

暴力的方法的复杂度依赖于 \(\max a\) 的大小，是因为因为这种方法不断去枚举 \(T\) 导致的。

其实枚举 \(T\) 是没必要的，因为很多操作是重复的。其实复杂度的瓶颈就是在于有些 \(a_i\) 很大，你不断减 \(1\) 很浪费时间。

所以可以在枚举 \(i\in [1,n]\)，考虑将每个敌人「杀死」，这么做是 \(O(n)\) 的。但是个人觉得代码不太好写，我使用的是二分。

由于 \(T\) 可以很大，事实上 \(T\in [1,(\max a) \times N]\)，考虑如下：

若存在一个最小的操作次数 \(T_{min}\)。则定 \(\forall T>T_{min}\)，这些 \(T\) 都多做了一些操作；\(\forall T<T_{min}\)，这些 \(T\) 都无法杀死所有敌人。

显然这道题符合二分的定义。

二分方法如下（会的直接跳过）

定义区间 \([L,R]\) 为查找区间，查找目的为 \(L+1=R\)。

• 如果 \(M=\frac{L+R}{2}\)，不足以杀死所有敌人，\(T_{min}\in(M,R]\)。
• 如果 \(M=\frac{L+R}{2}\)，能杀死所有敌人，是或不是最小次数（包含是最小次数的），\(T_{min}\in[L,M]\)。

判断是否杀死的方法：

定义 \(x\) 为当前消耗的 \(T\) 值。

对于 \(i\in [1,n]\)，记 \(y=a_i\)。

• 定义 \(m=3-(x \bmod 3)\)

  • 如果 \(y<m\)，令 \(x\) 为 \(x+y\)。

  • 如果 \(y\ge m\)，令 \(y\) 为 \(y-m-2\)，\(x\) 为 \(x+m\)。这里为了更好描述敌人的损耗。这是若 \(y\ge 0\)，则 \(i\) 已经死了。否则：设每轮 \(3\) 此共 \(5\) 伤害值的轮数 \(r=\lfloor\frac{x}{5}\rfloor\)，计算出 \(y\) 经过 \(r\) 轮伤害后的 \(y_1\)，同时更新 \(x\)。

    • 如果 \(y_1\in \{1,2\}\)，则 \(x\) 增加 \(y_1\)。
    • 否则，\(x\) 增加 \(3\)。

具体思想是循环问题，每 \(5\) 个伤害为一轮，可仔细体会。

运用上面的方法，判断 \(i\) 次后是否满足 \(x\leq T\) 即可。

以上就是数学的描述，下面就是代码：

// #define EXT
#include <bits/stdc++.h>
#ifdef EXT
    #include <bits/extc++.h>
#endif

//define
#define i64 long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define fdn(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>

using namespace std;

// type define
typedef long long ll;
typedef double db;
typedef __int128 i128;
#ifdef EXT
    typedef unsigned int ui;
    typedef unsigned long long ull;
    typedef long double ldb;
#endif

// const integer
const int INF=1<<29;
const ll INFL=1ll<59;
const int N=2e5+3;

int n;
ll a[N],sum[N];

bool check(ll t)
{
    ll x=0;
    rep(i,1,n)
    {
        ll m=3-x%3;
        ll y=a[i];
        if(y<m) x+=y;
        if(y>=m)
        {
            // remaining : 3
            // x=0,1,2,3 m=3
            y=y-m-2,x+=m;
            if(y<=0) continue;
            // remaining : 7
            // x=0,1,2,3 m=3
            // y=2;
            ll r=y/5;x+=3*r;
            ll r0=y-5*r;
            if(r0<=2) x+=r0;
            else x+=3;
        }
    }
    return x<=t;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    rep(i,1,n) cin>>a[i],sum[i]=sum[i-1]+a[i];
    ll l=0,r=N*1e9+23;
    while(l+1<r)
    {
        ll mid=l+((r-l)>>1);
        if(check(mid))
            r=mid;
        else l=mid;
    }
    cout<<r;
}

代码中穿插了我写代码是举的例子，可仔细体会。

总结

我觉得这次很难。

广告：安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。