题解：【ABC368 C】Triple Attack

JXR_Kalcium · 2024-08-25 08:00:31 · 题解

题目大意

给定一个长为 N 的序列 H，给定 T=0，每次进行下面的操作直到序列 H 全变为非正数：将 T 增加一，如果 T 为 3 的倍数就将最前面为正数的 H_i 减少 3，否则减少 1，问最后的 T 值。

解题思路

因为样例 3 中的 T 达到了 3\times 10^9，所以暴力模拟肯定不行。可以发现，每次操作后减少的数应为 1,1,3,1,1,3,\cdots，所以我们可以把 1,1,3 看成一个整体，让 H_i 直接先把所有的 1,1,3 跳完，剩下的再通过暴力跳就可以了。

AC 代码

#include <bits/stdc++.h>
#define ll long long
#define endl putchar(10)
#define spc putchar(32)
#define R register
using namespace std;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " = " << x, endl
#endif

inline ll read()
{
    ll x=0,f=1; char c=getchar();

    while(c<48 || c>57)
    {
        if(c=='-') f=-1;
        c=getchar();
    }

    while(c>47 && c<58)
    x=(x<<1)+(x<<3)+c-48, c=getchar();
    return x*f;
}

inline void write(ll x)
{
    static ll sta[41]; ll top=0;
    if(x<0) putchar('-'), x=-x;
    do sta[top++]=x%10, x/=10; while(x);
    while(top) putchar(sta[--top]+48);
}

ll n,h,ans,k=3;

int main()
{
    n=read();

    for(int i=1; i<=n; ++i)
    {
        h=read();
        if(k<2) --h,++k,++ans; 
        if(k==2 && h>0) h-=3,++k,++ans;
        if(h<1) continue;
        ans+=h/5*3; h%=5;
        if(h && h<3) k=h,ans+=h;
        else if(h>2) k=3,ans+=3;
    }

    write(ans);
    return 0;
}