第2篇

#include<iostream>

int main()
{
    int d;
    std::cin >> d;
    char s[1000];
    int size = 0;
    char c;
    while (std::cin >> c){
        while (size > 0 and d > 0){
            char top = s[size - 1];
            if (top < c){
                d--;
                size--;
            }
            else{
                break;
            }
        }
        s[size++] = c;
    }
    while (d > 0){
        d--;
        size--;
    }
    for (int i = 0; i < size; ++i) {
        std::cout << s[i];
    }
}

记循环 while (std::cin >> c) 执行了 $n$ 次，该程序的时间复杂度为（ ）。

{{ select(1) }}

• $\Theta(n)$
• $\Theta(nd)$
• $\Theta(n\log n)$
• $\Theta(n+d)$