题解 | #DNA序列#

#include <iostream>
using namespace std;

int main() {
    string str;
    int len;
    cin >> str >> len;
    // 滑动窗口
    // 计算子串的CG比例
    auto computeRatio = [] (string subStr) {
        int count = 0;
        for (auto& c : subStr) {
            if (c == 'C' || c == 'G') {
                count++;
            }
        }
        return double(count) / double(subStr.size());
    };
    double maxRatio = 0;
    // 维护有最大比值的左右区间
    int leftMax = 0, rightMax = str.size();
    for (int i = 0, j = len; j <= str.size(); j++) {
        // 如果当前区间大于len
        while (j - i >= len) {
            // 获取当前的子串及比率
            auto curStr = str.substr(i, j - i);
            auto curRatio = computeRatio(curStr);
            // 如果比最大比率大，更新左右区间和比率
            if (curRatio > maxRatio) {
                leftMax = i;
                rightMax = j;
                maxRatio = curRatio;
            }
            // 将左端点溢出
            i++;
        }
    }
    cout << str.substr(leftMax, rightMax - leftMax) << endl;
}
// 64 位输出请用 printf("%lld")