CCC 2022 S3题解核心代码疑问：cur变量逻辑解析求助

我参加完2022年Cool Clarinet Competition（CCC）后，研究了S3《Good Samples》题的C++题解，已经理解了通过控制独特/非独特音符来匹配k个good samples的整体思路，但对核心代码中ll cur = min(k-rem, m);这一行的逻辑存在疑问。已知cur变量需要实现三个功能：1. 控制选择独特/非独特数字；2. 限制数值不超过m；3. 确定非独特数字的取值。下面就来拆解这行代码的工作原理，纠正可能的理解偏差。

原题要求 #

构造含n个音符（音高为≤m的正整数）的乐曲，使其中恰好有k个good samples（无重复音高的连续非空子序列）。

题解代码与示例 #

题解代码 #

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;
using ll = long long;

ll min(ll a, ll b){return a > b ? b : a;}

void solve(){
    ll n,m,k; 
    cin>>n>>m>>k;
    vector<ll> ans; 
    for(ll i=0;i<n;i++)
    {   
        ll rem = n-i-1;
        ll cur = min(k-rem, m);
        if(cur<=0) break;  
        ll val;
        if(cur > i)//添加独特音符
        {   
            val=min(m,i+1);
            cur=val; 
        }
        else{ //添加非独特音符
            val=ans[i-cur]; 
        }
        ans.push_back(val);
        k = k - cur;
    }
    if(k==0 and (ll)ans.size()==n)
    {
        for(auto x: ans) cout<<x<<' '; 
        cout<<endl; 
    }
    else cout<<-1<<endl;
}

int main(void){
    solve();
    return 0;
}

输入输出示例 #

• 输入：4 3 9
• 输出：1 2 3 1
• 解释：符合条件的good samples共9个，分别为(1), (1,2), (1,2,3), (2), (2,3), (2,3,1), (3), (3,1), (1)

核心代码cur = min(k-rem, m)解析 #

首先明确rem的含义：rem = n-i-1，代表当前构造第i个音符（从0计数）时，后面还剩下的音符数量。

1. k - rem的逻辑 #

当构造第i个音符时，剩下的rem个音符最多能贡献rem个good samples（每个单独的音符）。为了让最终总数量恰好为k，当前步骤最多只能从第i个音符这里拿走k - rem个good samples——如果拿多了，剩下的音符就算全贡献单个样本也凑不够k；如果拿少了，后续还能补充。这一步是计算当前音符能贡献的最大合理数量，保证后续有调整空间。

2. 和m取最小值的原因 #

一方面，每个音符的音高不能超过m；另一方面，当添加独特音符时，最多只能有m个不同的音高，所以cur不能超过m，否则逻辑上无法实现（比如m=3，不可能出现第4个独特音高）。这直接对应cur的第二个功能：限制数值不超过m。

3. cur如何实现三个核心功能 #

• 控制独特/非独特选择：后续通过cur > i判断。i是当前已构造的音符数量（循环从0开始，i等于已添加元素个数），如果cur > i，说明当前需要添加独特音符（已有的i个都是独特的，最多能有i+1个独特的，此时cur要求的数量超过已有的数量，只能新增独特音符满足）；否则就添加非独特音符，复用之前的音高。
• 限制数值不超过m：通过min(..., m)直接限制cur的上限，同时添加独特音符时，val=min(m,i+1)再次确保音高不超过m。
• 确定非独特音符的取值：添加非独特音符时，val=ans[i-cur]，cur决定了复用哪个位置的音高。这样做的目的是，当前音符加入后，新增的good samples数量恰好是cur个：复用i-cur位置的音高，意味着从i-cur+1到i的子序列中，只有长度为1到cur的连续子序列是无重复的（到cur长度时会遇到重复音高），刚好贡献cur个新的good samples。

结合输入示例验证 #

输入n=4, m=3, k=9：

• 第1次循环（i=0）：rem=3，cur=min(9-3,3)=3。cur>0，进入独特分支，val=min(3,1)=1，cur设为1。ans添加1，k=9-1=8。
• 第2次循环（i=1）：rem=2，cur=min(8-2,3)=3。cur>1，进入独特分支，val=min(3,2)=2，cur设为2。ans添加2，k=8-2=6。
• 第3次循环（i=2）：rem=1，cur=min(6-1,3)=3。cur>2，进入独特分支，val=min(3,3)=3，cur设为3。ans添加3，k=6-3=3。
• 第4次循环（i=3）：rem=0，cur=min(3-0,3)=3。cur<=3，进入非独特分支，val=ans[3-3]=ans[0]=1。ans添加1，k=3-3=0。
  循环结束，k=0且ans长度为4，输出符合要求。

内容的提问来源于stack exchange，提问作者Ethan Ma