坏掉的项链(洛谷P1203题题解,C++语言描述)

题目要求

题目链接

坏掉的项链(洛谷P1203题题解,C++语言描述)

分析

链子是循环的,随便选一点断开不合适,所以把它作为一个线性的字符串其实不好。

处理方法是将字符串扩增一倍,即necklace += necklace;

这样的话,我们从初始出发,必然能遍历整个链子且不受出发点的影响。

我的思路类似于非递归的斐波那契数列,设置一个prev一个temp,比较result和prev+temp的大小,取最大值。

遍历的时候细节有很多:

  1. 先初始化prev,要小心w作为开头,因为w相当于邻近的r或b
  2. 每一轮都考虑当前r或b,尽可能多地取,包含w也取下来,统计temp
  3. r e s u l t = m a x ( r e s u l t , t e m p + p r e v ) result = max(result, temp+prev) result=max(result,temp+prev)
  4. 更新prev,不能更新为temp,而还要考虑到本轮初始的i前面的w,所以要加上

于是乎,我WA了三个数据点,如下:

测试用例2输入:

3
rrr

测试用例2输出:

3

测试用例4输入:

17
wwwwwwwwwwwwwwwww

测试用例4输出:

17

测试用例6输入:

8
rrwwwwbb

测试用例6输出:

8

分别是三处细节问题,本质是一样的,即我没有考虑到一遍就跑完的情况,重复导致额外多加了很多。

处理方法是补充原则性判断 i < n i < n i<n 和 t e m p + p r e v ≤ n temp+prev ≤ n temp+prev≤n

代码有注释,自行食用!

推荐好的题解,但确实难懂,各位大神耗子尾汁。

AC代码

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int n, prev = 0, temp, result, i = 0, j;
    string necklace;
    cin >> n >> necklace;
    // 复制一份
    necklace += necklace;
    char prev_c, temp_c;
    // 合并最初的w
    while ((necklace[i] == 'w') && i < n) {
        prev++;
        i++;
    }
    // 初始化找出第一个prev 包含当前或w
    prev_c = necklace[i];
    // 限制防止跑两遍
    while ((necklace[i] == prev_c || necklace[i] == 'w') && i < n) {
        prev++;
        i++;
    }
    result = prev;
    // 否则会双倍
    if (i < n) {
        // 正式开始遍历
        for (; i < 2*n;) {
            temp = 0;
            temp_c = necklace[i];
            // 反向遍历找出前方w数
            j = i-1;
            // 合并之前的w
            while (necklace[j] == 'w') {
                j--;
            }
            j = i-j-1;
            // 找出当前temp 包含当前或w
            while (necklace[i] == temp_c || necklace[i] == 'w') {
                temp++;
                i++;
            }
            if (temp+prev <= n) {
                result = max(result, temp+prev);
            }
            // 由于每一个temp只考虑它和它后面的w,不考虑前面的w,所以当变成prev前要把当前temp的数量加上之前的w个数
            prev = temp+j;
        }
    }
    cout << result;
    return 0;
}
上一篇:LFU缓存结构


下一篇:LinkedList