K15361 - 质量检测简化版（quality）请用C + +算法实现 题目描述 小科的妈妈在质检局工作，根据工作安排，今天她要去红星零件厂检查某种新型零件的合格率是否满足国家规定的质量要求。小科的妈妈和以往一样，带了一个长度为k的放大镜，可以一次性检测k个零件，原本红星修理厂该零件一批次只会生产k个，但是由于疫情期间贸易交通不便，红星修理厂一共积压了n(n大于k)个该零件，n个零件呈一条直线排列在车间里，每个零件按质量分等级，最高为A，然后依次是B,C,D,E,F，根据国家规定，质量等级达到某个等级的零件被认为是合格零件。小科的妈妈利用她带来的放大镜，只检测一次连续的k个零件，问她这一次检测中最多会有多少个合格产品。 输入格式 输入共四行 第一行 一个整数，表示待检测零件数量n（10<=n<=1000）； 第二行 n个字符，分别n个零件的质量等级(质量等级从高到低为A,B,C,D,E,F，全为大写字母且不包含空格)； 第三行 一个字符表示合格零件的质量等级要求（可能值为A,B,C,D,E,F）； 第四行 一个整数表示小科妈妈放大镜的长度k（5<=k<=10）； 输出格式 输出一行，输出小科妈妈这一次检测中最多会有多少个合格的产品。 输入输出样例 输入样例1：复制 20 AACCFDABCDEFAABCDEFD C 10 输出样例1：复制 7 说明 样例1解释： 检测AACCFDABCD这一段，合格零件个数最多为7个

<think>嗯，我现在需要解决这个问题。题目大意是说，给定n个零件的质量等级排列，然后用一个长度为k的放大镜去检测连续的k个零件。找出其中合格数量最多的一段，输出最大值。那合格的条件是零件的等级等于或优于给定的要求等级。比如，如果合格等级是C，那么A、B、C都算合格，而D、E、F不算。 首先，我得仔细看一下输入输出。输入包括n，然后是n个字符的字符串，第三行是合格等级，第四行是k。输出是最大的合格数量。 那问题可以拆解成几个步骤： 1. 确定哪些字符是合格的。比如，合格等级是C的话，那么所有字符是A、B、C的都算合格。所以需要根据输入的合格等级，确定哪些字符满足条件。 2. 然后，遍历所有长度为k的连续子串，计算每个子串中有多少个合格的字符，找出最大值。 那怎么处理合格等级的判断呢？比如，A的等级最高，F最低。如果给定的合格等级是C，那么所有等级高于等于C的（即A、B、C）都算合格。所以需要建立一个等级顺序的映射，比如A是0，B是1，C是2，D是3，E是4，F是5。然后输入的合格等级对应的数字，比如如果是C的话，对应数字是2。所有字符等级对应的数字小于等于2的就是合格。 那步骤可能是这样的： - 预处理每个字符对应的数值，比如A到F对应0到5。 - 根据输入的合格等级，得到阈值threshold。例如输入是C，则threshold是2。 - 遍历原字符串中的每个字符，将每个字符转换为是否合格（即是否其对应的数值<=threshold）。 - 这样得到一个布尔数组，或者直接保存为0和1的数组，其中1表示合格，0不合格。 - 然后，找出所有连续k个元素的窗口中，1的总数的最大值。这可以用滑动窗口的方法优化。 那滑动窗口的优化是关键。例如，初始时计算第一个窗口的和。然后每次滑动窗口时，减去离开窗口的元素的值，加上新进入窗口的元素的值，然后比较最大值。 具体步骤： 1. 将输入的字符串转换成每个字符是否合格的情况。比如，合格等级是C，那么字符如果是A、B、C则标记为1，否则0。 这一步需要注意字符的大小写，但题目中说明输入都是大写字母，所以不用担心。 2. 计算所有长度为k的窗口中的1的数量之和，找到最大的那个。 那么如何高效计算这些窗口的总和？ 滑动窗口法的时间复杂度是O(n)，而暴力方法的时间复杂度是O(n*k)。当n较大时（比如1000），k=10的话，暴力法的话是1000*10=1e4次操作，应该也是可以的。不过，滑动窗口更高效一些。 那滑动窗口如何实现？ 初始化max_sum和current_sum。current_sum初始化为前k个元素的和。然后，从第k个元素开始，每次加上下一个元素，减去第一个元素，然后更新max_sum。 比如，假设数组是arr，每个元素是0或1。 current_sum = sum(arr[0..k-1]) max_sum = current_sum 然后，对于i从k到n-1： current_sum += arr[i] - arr[i -k] max_sum = max(max_sum, current_sum) 这样就能得到最大值。 那这样就可以在O(n)的时间内完成。 现在需要考虑边界情况，比如当k等于n的时候？但题目中n>k的情况不存在，题目中说n>k吗？题目描述里说n大于k。比如输入样例中的n是20，k是10。所以输入的n肯定大于等于k？不，题目中说n大于k？原题描述第三段输入样例的n是20，k是10，说明n大于k。那题目中的输入条件是否保证n>=k？ 原题题目描述中说：输入n是待检测的零件数量，且n>k？比如题目描述里的第三段输入样例中n是20，k是10。原题给出的输入格式第四行是k的值，所以可能存在n >=k吗？ 原题输入格式中，第一行的n的条件是10<=n<=1000，第四行的k是5<=k<=10。所以可能n等于k吗？比如n=10，k=10？这时候窗口只能是整个数组。所以代码中必须处理这种情况。 但原题中的题目描述中，“红星修理厂一共积压了n（n大于k）个该零件”，所以输入的n一定大于k？所以可能题目保证n>k？那在代码中是否需要处理n等于k的情况？ 或者原题中的n可能等于k吗？原题输入中的第一行是n，可能用户输入的n是等于k吗？比如n=5，k=5？但题目中说n大于k吗？ 题目描述中的第一句话：“红星修理厂一共积压了n(n大于k)个该零件”，所以输入的n肯定是大于k的。所以代码中不需要处理n等于k的情况？ 那可能输入的n一定大于k？所以程序可以假设输入的n>k。但用户是否可能输入n等于k？比如原题中的输入样例中的n是20，k是10。所以可能需要处理n>=k的情况？ 可能题目中的输入条件中n是大于等于k的吗？或者题目中的n>k？ 根据题目描述中的括号里的说明，n大于k。那输入的n的值肯定满足n>k，所以程序可以假设输入的n>k。这样在代码中不需要处理n等于k的情况。例如，用户输入的n是10，k是5，那么n>k成立。所以代码中可以安全地处理所有窗口的情况。 那现在回到问题，如何处理？ 步骤： 1. 读取输入： - 第一行读n，第二行读n个字符组成的字符串，第三行读合格等级，第四行读k。 注意，输入的第三行可能包含多个字符吗？比如可能输入的是多个字符？根据题目描述，第三行是一个字符，所以第三行的输入应该是一个字符。需要确保读取的时候正确。 比如，用C++的话，第三行可能后面有一个换行符，需要注意处理输入中的换行符。 比如，在读取第三行的合格等级时，可能前面有换行符未被读取，所以需要处理。 具体来说： 读取n之后，可能会有换行符留在输入流中。然后读取第二行的字符串，可能用cin.getline或者cin.ignore处理掉换行符？或者用getline读取整行？ 例如： cin >> n; 然后，读取第二行的字符串。如果第二行的字符串是连续字符，没有空格，那么可以用cin >> string，但需要注意n的个数是否正确。或者，可能第二行的输入是n个字符，中间可能有空格吗？题目中说“n个零件的质量等级，全为大写字母且不包含空格”，所以第二行的输入是一个连续的字符串，长度为n。所以可以直接读取一个长度为n的字符串。 第三行的输入是一个字符，所以可以用cin读取，注意跳过前面的换行符。比如： cin.ignore(); 或者用getchar()来读取换行符。 例如，在C++中： int n; cin >> n; string s; cin >> s; // 这里需要确保s的长度是n吗？题目中说输入的是n个字符，所以应该保证s的长度等于n。 char level; cin >> level; // 可能会出错，因为前面输入s之后，用户可能输入了换行符。所以需要用cin.ignore()来跳过。 或者，用cin的格式化输入： cin >> n; cin.ignore(); // 跳过n之后的换行符 getline(cin, s); // 读取第二行的n个字符。但可能s中有换行符吗？题目中说明第二行的输入是n个字符，没有空格，所以用getline的话可能会包含换行符？或者可能用cin >> s，假设输入的字符串没有空格，并且正确读入n个字符？ 例如，假设用户输入第二行的字符串是例如"AACCFDABCDEFAABCDEFD"，那么cin >> s会正确读取这个字符串，但是需要确保输入中没有空格，且长度为n。但是用户输入时可能输入换行符或其他，导致问题。但在算法题中，通常假设输入是正确的，所以可以忽略这个问题。 然后第三行是单独的一个字符，如输入样例中的第三行是C。所以可以用cin >> level吗？ 可能需要注意，在读取第二行的字符串之后，可能有一个换行符未被读取，所以第三行的输入需要用cin.ignore()来跳过前面的换行符。 例如： cin >> n; string s; cin >> s; char qual_level; cin >> qual_level; int k; cin >>k; 这可能会有问题，因为当输入第二行的字符串后，输入指针可能在换行符之后。比如，假设输入样例中的输入： 20 AACCFDABCDEFAABCDEFD C 10 当读取第二行的字符串时，cin >> s会读取"AACCFDABCDEFAABCDEFD"，然后第三行是C，所以cin >> qual_level会读取C，然后第四行的10会被读取到k。 这应该没有问题，因为cin会自动跳过空白符。例如，cin >> s读取字符串后，后面的换行符会被cin的>>操作自动跳过。所以第三行的读取应该没问题。所以不需要额外的处理。 不过，可能在实际测试中，输入的方式可能会影响结果。比如，如果第二行的字符串后面没有换行符的话，可能会有问题？但按照题目样例，输入应该是正确的。 所以这一步的代码大致是： int n; cin >> n; string s; cin >> s; char qual_level; cin >> qual_level; int k; cin >>k; 然后需要处理字符串s的长度是否为n？题目中保证输入正确，所以不需要检查。 接下来，确定合格等级的阈值。比如，qual_level对应的数值是否小于等于该数值的字符合格。 我们需要将字符A-F转换为对应的数值：A是0，B是1，C是2，D是3，E是4，F是5。因此，当给定的qual_level是C时，对应的数值是2，所有字符的数值<=2的（即A、B、C）合格。 所以，对于输入的qual_level字符，转换为对应的数值threshold。例如，如果qual_level是C，则threshold=2。 然后，将字符串s中的每个字符转换为是否合格，即该字符对应的数值是否<=threshold。例如，字符是A，那么数值0，是否<=threshold？是的，所以合格，标记为1。否则0。 这一步可以预先处理得到一个数组，比如vector<int> valid(n)，其中valid[i]为1或0。 然后，计算所有连续k长度的子数组的和的最大值。这可以用滑动窗口法。 例如： 初始化current_sum为前k个元素的和。 然后，从i=k到n-1的位置，每次current_sum += valid[i] - valid[i -k]，并比较max_sum。 比如： int max_sum = 0; int current_sum = 0; // 初始化前k个元素的和 for(int i=0; i<k; i++){ current_sum += valid[i]; } max_sum = current_sum; for(int i=k; i <n; i++){ current_sum += valid[i] - valid[i -k]; if(current_sum > max_sum){ max_sum = current_sum; } } 这样就能得到最大的合格数量。 那现在的问题是，如何将qual_level转换为对应的threshold数值？ 例如，如果qual_level是A，threshold是0；B是1，等等。可以通过字符到数值的映射。例如： char c = qual_level; int threshold = c - 'A'; 因为A的ASCII码减去A的ASCII码是0，B是1，等等。所以这个转换是正确的。 然后，对于每个字符s[i]，其对应的数值是s[i] - 'A'。如果这个值 <= threshold，则合格，否则不合格。 所以，预处理valid数组： vector<int> valid(n); for(int i=0; i<n; i++){ int val = s[i] - 'A'; valid[i] = (val <= threshold) ? 1 : 0; } 这样，valid数组中的每个元素是1或0，表示对应的零件是否合格。 那现在，使用滑动窗口法计算最大的和即可。 现在，将所有步骤组合起来，代码的大致结构如下： 读取输入n, s, qual_level, k. 计算threshold = qual_level - 'A'. 预处理valid数组。 计算滑动窗口的最大和。 输出max_sum. 这应该就能得到正确的结果。 现在测试样例： 输入样例1： 20 AACCFDABCDEFAABCDEFD C 10 对应的threshold是2（C的数值是2）。 字符串中的每个字符对应的数值是否<=2？ 原字符串是"AACCFDABCDEFAABCDEFD"。 转换为数值： 字符序列：A A C C F D A B C D E F A A B C D E F D 对应的数值： 0,0,2,2,5,3,0,1,2,3,4,5,0,0,1,2,3,4,5,3. 然后，判断每个是否<=2： 0（是）→1 0→1 2→1 2→1 5→0 3→0 0→1 1→1 2→1 3→0 4→0 5→0 0→1 0→1 1→1 2→1 3→0 4→0 5→0 3→0. 所以valid数组是： 1,1,1,1,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,0. 然后k=10，要找连续的10个元素中和最大的。 那么原样例中的最佳窗口是前10个元素： 索引0-9对应的valid值是：1,1,1,1,0,0,1,1,1,0。总和是1+1+1+1+0+0+1+1+1+0=7。所以输出7。 根据样例说明，输出是7，正确。 所以代码应该正确。 现在编写C++代码： 需要考虑可能的输入输出问题，比如如何处理第三行的输入。 代码大致结构： #include <iostream> #include <string> #include <vector> using namespace std; int main() { int n; cin >> n; string s; cin >> s; char qual_level; cin >> qual_level; int k; cin >> k; int threshold = qual_level - 'A'; vector<int> valid(n); for(int i=0; i<n; i++){ int val = s[i] - 'A'; valid[i] = (val <= threshold) ? 1 : 0; } int current_sum =0; for(int i=0; i<k; i++){ current_sum += valid[i]; } int max_sum = current_sum; for(int i=k; i <n; i++){ current_sum += valid[i] - valid[i -k]; if(current_sum > max_sum){ max_sum = current_sum; } } cout << max_sum << endl; return 0; } 这个代码应该能正确处理样例输入。 测试样例输入： 输入样例1的输入： 20 AACCFDABCDEFAABCDEFD C 10 代码处理后的valid数组前10个元素是1,1,1,1,0,0,1,1,1,0。总和是7。所以输出7。正确。 另一个测试情况，例如，当k等于n的情况？但根据题目描述，n>k，所以不会有这种情况。但是程序中如果k等于n，代码仍然可以处理吗？ 比如，假设n=10，k=5。那么current_sum初始化为前5个元素的和，然后循环从5到9（i=k=5到i=9，循环条件是i <n=10）。每次i从5到9，共5次循环。例如： i=5：current_sum += valid[5] - valid[0] i=6： += valid[6] - valid[1] i=7： += valid[7] - valid[2] i=8： += valid[8] - valid[3] i=9： += valid[9] - valid[4] 然后，在每次循环后，current_sum是窗口i-k+1到i的和。比如，当i=5时，窗口是1-5，对吗？ 或者，原滑动窗口的逻辑是否是正确的？ 比如，初始窗口是0到k-1（索引0到k-1）。 然后，i从k到n-1： 窗口是 [i -k +1, i]？ 例如，当i=k时，窗口是1到k。current_sum的计算是加上valid[k]（即第k+1个元素）并减去valid[0]。所以，新的窗口是1到k。对的。 所以，当k等于n时，假设n=5，k=5。此时，初始current_sum是sum(0-4)，然后循环i从5到n-1，即i=5，但n=5时循环不执行。所以max_sum就是初始的sum，正确。 所以，不管k的值如何，只要k<=n，代码都能正确执行。题目中n可能等于k吗？根据题目描述，n>k，所以不需要处理，但代码仍然可以处理。 综上，这个代码应该是正确的。</think>```cpp #include <iostream> #include <string> #include <vector> using namespace std; int main() { int n; cin >> n; string s; cin >> s; char qual_level; cin >> qual_level; int k; cin >> k; int threshold = qual_level - 'A'; vector<int> valid(n); for (int i = 0; i < n; ++i) { int val = s[i] - 'A'; valid[i] = (val <= threshold) ? 1 : 0; } int current_sum = 0; for (int i = 0; i < k; ++i) { current_sum += valid[i]; } int max_sum = current_sum; for (int i = k; i < n; ++i) { current_sum += valid[i] - valid[i - k]; if (current_sum > max_sum) { max_sum = current_sum; } } cout << max_sum << endl; return 0; } ``` ### 步骤解释 1. **输入处理**：读取零件数量 `n`、质量等级字符串 `s`、合格等级 `qual_level` 和放大镜长度 `k`。 2. **确定合格标准**：将合格等级转换为阈值 `threshold`（例如，'C' 转换为数值2）。 3. **预处理合格标记数组**：遍历质量字符串，生成对应的合格标记数组 `valid`，合格为1，不合格为0。 4. **滑动窗口计算最大值**： - 初始计算前 `k` 个零件的合格数。 - 滑动窗口逐个移动，更新当前窗口的合格数，并记录最大值。 5. **输出结果**：打印检测窗口内最多合格零件数。