【題解】Codeforces GYM 101652 S.Purple Rain

【題目敘述】http://codeforces.com/gym/101652/attachments Problem S
【解題想法】最大連續和跑兩遍

#include <bits/stdc++.h>
using namespace std;
 
string s;
int mx, tot, l, r, tmpl;
 
int main(){
    cin >> s;
    tmpl = 1;
    for (int i = 1; i <= s.length(); i++){
        if (s[i-1] == 'R') tot++;
        else tot--;
        if (tot > mx){
            l = tmpl;
            r = i;
            mx = tot;
        }
        if (tot < 0){
            tot = 0;
            tmpl = i+1;
        }
    }
    tmpl = 1;
    tot = 0;
    for (int i = 1; i <= s.length(); i++){
        if (s[i-1] == 'R') tot--;
        else tot++;
        if (tot > mx){
            l = tmpl;
            r = i;
            mx = tot;
        }
        if (tot == mx && tmpl < l){
            l = tmpl;
            r = i;
        }
        if (tot < 0){
            tot = 0;
            tmpl = i+1;
        }
    }
    cout << l << " " << r << "\n";
}
分享本文 Share with friends