https://www.acmicpc.net/problem/10799

質問する

何本もの鉄棒がレーザーで切らなければならない.効率的に動作するために、鉄棒を下から上へ重ね、上から垂直にレーザーを発射し、鉄棒を切断します.鉄棒とレーザーの配置は以下の条件を満たす:
鉄の棒は自分より長い鉄の棒にしか置けません.鉄棒を別の鉄棒の上に置くと、端点が重ならないように完全に含まれるように配置されます.
各鉄棒を切断するレーザー光は少なくとも1つ存在する.
レーザーはいかなる鉄棒の両端にも重ならない.
次の図は、上記の条件を満たす例を示しています.水平に描かれた太い実線は鉄棒で、点はレーザーの位置で、垂直に描かれた破線の矢印はレーザーの発射方向です.

これらのレーザーと鉄棒の配置は、括弧で左から右に順に表すことができます.

レーザーは、左かっこと右かっこの隣接するペア「()」として表されます.また、すべての「()」はレーザー光を表す必要があります.
鉄棒の左端は左かっこ「(」,右端は右かっこ「)」で表される.
前例のカッコは図に表されます.

鉄棒はレーザで数枚に切断され、上記の例では、最上位の2本の鉄棒はそれぞれ3枚と2枚に切断され、このようにして与えられた鉄棒は全部で17枚に切断された.

鉄棒とレーザーの配置を表す括弧が与えられた場合、切断された鉄棒片の総数を求めるプログラムを作成してください.

入力

鉄棒とレーザの配置を表す括弧を1行に空白なく与えた.かっこ文字の個数は最大100000です.

しゅつりょく

切り取られた破片の総数を表す整数を1行に出力します.

にゅうしゅつりょく

入力例1

()(((()())(())()))(())

サンプル出力1

17

入力例2

(((()(()()))(())()))(()())

サンプル出力2

24

Solution

#include <iostream>
#include <stack>
using namespace std;

int main(){
    string tmp;
    stack<char> stk;
    int answer = 0;
    cin >> tmp;
    for(int i = 0; i < tmp.size(); i++){
        if(tmp[i] == '(') stk.push(i);
        else{
            if(tmp[i - 1] == '('){
                stk.pop();
                answer += stk.size();
            } 
            else{
                answer += 1;
                stk.pop();
            }
        }
    }
    cout << answer << '\n';
}

クレヨンしんちゃんをむやみになくしたら、それは頭が痛い問題です.実際に使えるものは何もありませんが、すでに入っているものを削除するのは難しいです.
初めて間違った問題を理解したのでリアルタイムで入力を受けましょうか?考えました.もちろん、そうしても問題は解決できますが、問題があります.
レーザーの後にパイプが破断した場合.では、どのように区別しますか?
別に違いはありませんが、面倒です.
だからインデックスで線形探索をしたいです.
「(」を見ると、パイプが始まっていると思ってスタークに押します.

 if(tmp[i] == '(') stk.push(i);

以前のやつは「(」を「インスタントラーメンレーザー」と見なしていた.最初は「("")のみ入れる」と遭遇するたびにstrepopを実行し、現在strepに格納されているデータ(パイプ数)をresh変数に加算した.

if(tmp[i - 1] == '('){
    stk.pop();
    answer += stk.size();
}

見つかったのはレーザーではなく、パイプの末端で、残りのパイプの破片を答えに保存するために+1を与えた.

else{
    answer += 1;
    stk.pop();
}

そんなに難しい問題はありません.今考えると銀色なら解けるんじゃないかな?