题解：P14796 [JOI 2026 二次预选] 究极团子达人 / Ultimate Dango Maker

dawn_pcx · 2025-12-20 11:36:38 · 题解

P14796

题目

题面其他题解够清晰，不多做叙述。

思路

这题需要 3 个差都 \leq1的团子组成串，我们就可以算 a_i 和 a_{i+1} 可以做几个团子串，先求出当前 a_i 的团子串数，计算 a_i 剩下的团子，如果 a_{i+1}\geq a_i，则将 a_{i+1} 减当前的 a_i ，团子串数 +1，继续遍历。

提醒

不开 long long 见祖宗！

AC Code

你们肯定都挺喜欢的。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[200005];

int main(){
    int n;
    cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll cnt=0;
    for(int i=1;i<=n;i++){
        cnt+=a[i]/3;//a[i] 有几个团子串
        a[i]=a[i]%3;//a[i] 剩下几个团子
        if(a[i]>0){//如果有剩下
            ll sum=3-a[i];//还差几个
            if(i+1<=n&&a[i+1]>=sum){//a[i+1] 不越界，且大于差的
                a[i+1]-=sum;//减去差的，剩下的
                cnt++;//团子串数量+1
            }
        } 
    }
    cout<<cnt;
    return 0;
}