C + + K15361 - 质量检测简化版（quality） 题目描述 小科的妈妈在质检局工作，根据工作安排，今天她要去红星零件厂检查某种新型零件的合格率是否满足国家规定的质量要求。小科的妈妈和以往一样，带了一个长度为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>嗯，我现在得仔细看看这个问题。题目是说，小科的妈妈要检测连续的k个零件，找出其中合格的最多的数量。那输入包括n个零件的等级，合格的标准是某个等级及以上。然后我需要找出所有连续的k长度的子数组中，合格的数量最多的那个值。 首先，我得理解问题。比如说，输入样例中的合格等级是C，那么所有等级为A、B、C的零件都是合格的。那在连续的k个零件中，统计这些符合条件的数量，然后找出最大的那个。 那怎么处理呢？可能的思路是滑动窗口。因为每次窗口移动一位，只需要去掉左边的一个，加上右边的一个，这样可以减少重复计算。不过，对于k比较小的情况可能差别不大，但n的范围到1000的话，滑动窗口的方式会更高效。 那具体步骤应该是： 1. 先确定合格的标准字符，比如输入是C的话，那么合格的等级是A、B、C。这时候需要把所有字符转化为是否合格的标志，比如0和1，或者True/False的数组。 2. 然后，遍历所有长度为k的连续子数组，计算其中合格的数量，记录最大的那个。这一步如果用滑动窗口的话，初始时计算第一个窗口的合格数，之后每次移动窗口，减去离开的元素，加上新进入的元素，这样时间复杂度是O(n)，而不用每次重新计算k次，这样效率更高。 那具体怎么实现呢？比如，先预处理一个数组，每个元素是1（合格）或0（不合格）。然后计算初始窗口的和，之后滑动时减去前面的元素，加上后面的元素。同时记录最大值。 那关键点有几个： - 如何确定哪些等级是合格的？比如输入的合格字符是C，那么所有字符<=C的都算合格。比如，字符的比较可以基于它们的ASCII码。例如，A的ASCII码最小，F最大。所以，如果合格线是C，那么字符的ASCII码小于等于'C'的字符都是合格的。因此，比较每个字符是否<=合格线字符即可。 这一步可能需要注意，题目中的等级是按从高到低排列的，所以A是最高，F是最低。或者题目描述中的质量等级是否顺序正确？例如，题目描述中说质量等级从高到低是A,B,C,D,E,F，那么A最好，F最差。而合格的要求是达到某个等级及以上。例如，如果合格标准是C，那么C及以上（即A、B、C）的零件是合格的？或者是否搞反了？ 这时候要看题目描述的准确意思。题目中说：“质量等级达到某个等级的零件被认为是合格零件”，这里的“达到”应该是指等于或更高。比如，假设等级顺序是A最高，F最低。那比如，当合格等级是C时，C及以上（即A、B、C）的零件是合格的。因为比如，比如在一般情况中，质量等级高意味着更好，所以要求“达到”某个等级，应该是指该等级或更高的等级才算合格。例如，当标准是C时，只有质量等级为C或更好的（A、B、C）才算合格。 所以，正确的处理方式是，将每个零件的等级字符与合格线字符比较，如果该字符<=合格线的字符，则视为合格。比如，合格线是C，那么A的ASCII码是65，B是66，C是67，所以所有字符的ASCII码<=67的（即A、B、C）都是合格的。 这一步非常重要，如果搞反了的话，整个答案都会错。比如，如果合格线是C，那么正确的合格条件是等级<=C吗？是的，因为A、B、C的等级高于或等于C吗？ 这里可能存在误解。例如，题目中说质量等级从高到低是A,B,C,D,E,F。那么A最高，F最低。所以，当合格标准是C时，所有质量等级不低于C的零件才算合格。那“质量等级达到某个等级”中的“达到”应理解为不低于该等级。例如，假设C是合格线，那么A、B、C的等级都是高于或等于C的，所以是合格的。而D、E、F则低于C，不合格。这个时候，正确的条件应该是零件的等级字符是否小于等于合格线字符？比如，合格线是C，所以字符<=C（即ASCII码<=67）的零件合格。是的，这样处理是对的。 举个例子，比如零件的等级是A，合格线是C。因为A比C高，所以是合格的。所以字符的比较是正确的。 那现在，如何将每个字符转化为是否合格呢？比如，对于每个字符c，如果c <= 合格线字符，则合格，否则不合格。 这一步处理正确的话，后续就可以统计窗口中的合格数量了。 那么具体步骤： 1. 读取输入：n，等级字符串，合格线字符，k。 2. 预处理每个字符是否合格，得到一个数组，比如合格为1，否则为0。 3. 使用滑动窗口计算最大的窗口和。即初始窗口的和是前k个元素的和，然后每次滑动窗口，减去滑出的元素，加上滑入的元素，同时记录最大值。 比如，初始窗口sum是前k个的和。然后从第k个位置开始到n-1的位置，每次sum = sum - arr[i -k] + arr[i]，然后比较max_sum。 或者，也可以用前缀和数组来计算每个窗口的和。比如，计算前缀和数组pre，其中pre[i]是前i个元素的和。那么窗口i到i+k-1的和是pre[i+k] - pre[i]。然后遍历所有可能的窗口，找到最大的值。这种方法的时间复杂度是O(n)，因为每个窗口的计算是O(1)，总共有n-k+1个窗口。 这两种方法的时间复杂度都是线性的，对于n=1000来说，都是可行的。 那具体如何实现呢？比如，用滑动窗口的话，可以先计算第一个窗口的合格数，然后滑动。或者用前缀和，可能更容易一些。 比如，假设预处理后的数组是valid，其中valid[i]是1或0。那么pre数组的长度是n+1，pre[0]=0，pre[i] = pre[i-1] + valid[i-1]。然后对于每个i从0到n-k，窗口的和是pre[i +k] - pre[i]。找到最大的这个值。 那这样实现起来比较方便。 那现在需要考虑输入的读取问题。比如，输入的第二行是n个字符，可能没有空格。比如样例输入中的第二行是“AACCFDABCDEFAABCDEFD”，共20个字符，对应于n=20的情况。所以在读取的时候，需要注意将第二行的字符串处理为一个字符数组，每个字符对应一个零件。 然后，第三行输入的是合格线字符，比如样例中是C。那么每个字符如果<=C的话，就是合格的。 然后，处理每个字符，得到valid数组。 接下来，计算前缀和数组。然后遍历所有可能的窗口，找到最大的sum。 所以，现在的问题转化为如何编写代码实现这些步骤。 比如，在C++中： - 读取n，可能需要注意换行符的问题。因为输入可能有四行，需要正确读取每行。 比如，输入样例中的四行： 20 AACCFDABCDEFAABCDEFD C 10 所以，读取的时候，第一行是n=20，第二行是字符串长度20，第三行是字符C，第四行是k=10。 代码的大致结构： 读取n。 读取第二行的字符串s。 读取第三行的字符c（合格线）。 读取k. 然后，预处理valid数组：对于每个字符在s中的字符，如果<=c，则valid[i] =1，否则0。 然后计算前缀和数组pre。 pre[0] =0. pre[i] = pre[i-1] + valid[i-1]. 然后，遍历所有可能的窗口起始点i，从0到n -k。窗口的sum是pre[i +k] - pre[i]。记录最大的sum。 最后输出这个最大值。 比如，在样例输入中，窗口长度k=10，n=20。所以窗口的数目是20-10+1=11个。其中，最大的sum是7，对应的窗口是前10个字符中的合格数。 比如，窗口是前10个字符：AACCFDABCD。对应的valid数组中的每个字符是否为合格？ 合格线是C，所以每个字符<=C的才合格。例如： 字符分别是A,A,C,C,F,D,A,B,C,D. 对应的valid数组是： A <=C →是 →1 A→1 C→1 C→1 F→F的ASCII码是70，C是67，所以F> C →0 D的ASCII码是68>67 →0 A→1 B→1 C→1 D→0。 所以前十个字符的valid数组是：1,1,1,1,0,0,1,1,1,0。总和是1+1+1+1+0+0+1+1+1+0=7，与样例的输出一致。 所以这个算法是正确的。 那现在要考虑代码中的各个步骤是否正确处理。 比如，如何处理输入的第三行？例如，第三行可能包含换行符或者空格？题目中说输入是四行，每行对应正确的数据。所以第三行是一个单独的字符，不带空格。所以在C++中，可以用cin或者getline的方式处理。需要注意，当读取第二行的字符串之后，可能会有换行符残留，所以在读取第三行的时候需要处理。 比如，在C++中，读取第二行的时候可能用cin >> s，但这样可能无法读取包含空格的情况。但题目中的输入第二行是没有空格的，所以没有问题。然后读取第三行的字符可以用cin，但需要注意前面是否有换行符。例如： 第二行用cin读取一个字符串，假设是s。此时，输入指针在第二行的末尾，换行符之后。然后第三行的字符会被cin读取吗？例如，假设第三行的输入是单独的字符，后面可能有换行符。此时，可以使用cin读取字符，或者用getchar()来处理。 比如，第三行的输入可能被cin视为一个字符，但要注意前后的空白。比如，第三行输入C，那么cin >> char会正确读取到C吗？ 例如，假设第三行是字符C，那么可以用以下方式： char standard; cin >> standard; 然后第四行的k用cin读取即可。 那这样处理是正确的吗？ 是的。因为当第二行的字符串被读取后，第三行的输入会被cin正确读取到字符变量中，而不会有问题。 然后，处理每个字符是否合格，循环遍历s中的每个字符，构造valid数组。 然后计算前缀和数组。然后遍历所有可能的窗口。 那现在代码的大体结构应该没有问题。 那现在测试样例是否正确？ 样例输入是： n=20 s= AACCFDABCDEFAABCDEFD →长度为20的字符串 standard是C →对应的合格条件是字符<=C →即A,B,C。 k=10. 那么最大的窗口是前10个字符，总和7。输出正确。 那现在，如何处理边界情况？ 比如，当n等于k的时候，整个数组就是一个窗口，直接计算即可。 当所有零件都不合格，那么输出0。 或者当k等于n的情况，这时候直接计算整个数组的和。 但题目中的n是大于k的。题目描述中说n大于k。但输入条件中的n是10<=n<=1000，而k是5<=k<=10。所以n必须大于等于10，k最多是10。那有可能n等于k吗？比如，n=10，k=10。但题目中的输入条件中n>k？或者题目描述中说“由于疫情期间，积压了n(n大于k)个零件”？原题中的问题描述中的输入条件是否n>k？ 看题目描述中的输入格式部分，第四行是k。题目描述中说“红星修理厂该零件一批次只会生产k个，但是由于疫情期间……积压了n（n大于k）个”，所以输入的n一定是大于k的。所以在代码中不需要处理n等于k的情况。所以所有输入的n都满足n>k。所以在代码中，窗口的数量是n -k +1 >= 1 +1=2吗？比如n=10，k=5的话，窗口数目是6。所以没有问题。 综上，代码的大致思路是正确的。 现在，如何编写代码？ 比如，在C++中： #include <iostream> #include <string> #include <vector> using namespace std; int main() { int n; string s; char standard; int k; cin >> n; cin >> s; cin >> standard; cin >> k; vector<int> valid(n); for (int i = 0; i < n; ++i) { valid[i] = (s[i] <= standard) ? 1 : 0; } vector<int> pre(n + 1, 0); for (int i = 1; i <= n; ++i) { pre[i] = pre[i - 1] + valid[i - 1]; } int max_count = 0; for (int i = 0; i <= n - k; ++i) { int current = pre[i + k] - pre[i]; if (current > max_count) { max_count = current; } } cout << max_count << endl; return 0; } 这样应该可以解决问题。需要注意pre数组的大小是n+1，初始化为0。然后pre[i]表示前i个元素的总和。当计算窗口i到i+k-1的和时，对应的pre数组的位置是i+ k - i之间的差，即pre[i +k] - pre[i]。 比如，窗口的起始位置是i（0-based），覆盖的元素是i到i +k-1。在pre数组中，pre[i +k]是前i +k个元素的总和，pre[i]是前i个元素的总和，所以差就是i到i +k-1的总和。 那这样计算是正确的。例如，第一个窗口i=0时，计算的是pre[k] - pre[0]，即前k个元素的和。这正确。 所以代码是正确的。 测试样例： 输入样例1中的n=20，k=10。窗口数目是20-10+1=11。其中最大的窗口总和是7。代码中的pre数组计算正确的话，应该得到正确结果。 综上，这个方法是正确的。</think>要解决这个问题，我们需要找出连续k个零件中合格数量的最大值。以下是逐步解决方案： ### 方法思路 1. **确定合格标准**：根据输入的合格等级字符，确定哪些零件是合格的。例如，若合格等级为C，则所有等级为A、B、C的零件均视为合格。 2. **预处理合格标志**：将每个零件转换为一个布尔数组（0或1），表示是否合格。 3. **滑动窗口计算最大值**：使用滑动窗口技术遍历所有可能的连续k个零件窗口，计算每个窗口内合格零件的数量，并记录最大值。 ### 解决代码 ```cpp #include <iostream> #include <string> #include <vector> using namespace std; int main() { int n; string s; char standard; int k; cin >> n; cin >> s; cin >> standard; cin >> k; vector<int> valid(n); for (int i = 0; i < n; ++i) { valid[i] = (s[i] <= standard) ? 1 : 0; } vector<int> pre(n + 1, 0); for (int i = 1; i <= n; ++i) { pre[i] = pre[i - 1] + valid[i - 1]; } int max_count = 0; for (int i = 0; i <= n - k; ++i) { int current = pre[i + k] - pre[i]; if (current > max_count) { max_count = current; } } cout << max_count << endl; return 0; } ``` ### 代码解释 1. **输入处理**：读取零件数量n、零件等级字符串s、合格等级字符standard和放大镜长度k。 2. **合格标志转换**：将每个零件的等级与合格等级比较，生成一个布尔数组valid，其中1表示合格，0表示不合格。 3. **前缀和数组**：计算前缀和数组pre，用于快速计算任意区间的和。 4. **滑动窗口遍历**：遍历所有可能的连续k个零件的窗口，利用前缀和数组快速计算每个窗口的合格零件数量，并更新最大值。 该方法通过预处理和滑动窗口技术高效地解决了问题，确保时间复杂度为O(n)，适用于较大的输入规模。