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

Chronomia_phi · 2025-12-20 08:27:22 · 题解

思路简述

由题意可知，制作串只可以使用相邻颜色的两种团子，或只使用一种颜色的团子。

那么我们可以从第 1 种颜色的团子开始遍历至第 n 种颜色的团子。对于每一种颜色的团子，我们尽量把它用完。

因此，遍历至第 i 种颜色的团子时：

• 先只用这种颜色的团子做串直到无法再做。

• 随后，再用与这种颜色团子相邻颜色的团子与该种颜色的团子做出尽量多的串。

  由于我们是从前往后遍历，前面的团子已经尽可能被消耗完全；因此只需要用当前颜色团子的后一种颜色团子，与当前颜色团子做出尽量串即可。

  也就是用第 i + 1 种颜色的团子与当前的第 i 种团子做出尽量多的串。

  （由于当前余下部分团子是只用当前颜色团子尽可能做更多串后所得，因此余下部分一定小于3个，最多再与其后一种颜色团子再做出一个串。）

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 100;
int n, a[N]; 
long long ans;

int main(){

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    } //输入
    for(int i = 1; i <= n; i++){

        ans += a[i] / 3; //用第 i 种团子做尽量多的串
        a[i] %= 3; //记录余下部分数量
        if(!a[i]) continue; //若没有余下的，那么遍历下一种
        int jl = 3 - a[i]; //记录还需要多少个团子可以与余下部分做出一个串

        if(i <= n-1 && a[i + 1] != 0){ 

            if(a[i + 1] >= jl){ //如果后一种团子可以与当前余下部分做出一个串

                a[i + 1] -= jl;
                ans++;

            }
        }

    }
    cout << ans; //输出
    return 0;
}