оптимизация кода

@Tolyas · Регистрация: 18.10.2011

Студворк — интернет-сервис помощи студентам

Задача: определить, является ли последовательность скобок действительной. Длинна строки не превышает 100000.
Например:
№ Input Output
1 ()(()) VALID
2 )( INVALID

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <string>
 
using namespace std;
 
int main()
{
    int sum=0;
    char *c = new char[100001];
    cin>>c;
    for(int i = 0 ;i<strlen(c);i++)
    {
        if (c[i]=='(')
            sum++;
        if (c[i]==')')
            sum--;
        if (sum<0 || sum>strlen(c)-i-1)
            break;
    }
    if(sum == 0)
        cout<<"VALID";
    else
        cout<<"INVALID";
    return 0;
}

Код не проходит по времени. Заранее спасибо.

@diagon · 20.04.2013, 22:33

Сообщение от Tolyas

i<strlen(c)

заменить на

C++
1
c[i]

А то у вас сложность квадратичная :)

Добавлено через 1 минуту

Сообщение от Tolyas

sum>strlen(c)-i-1

и вот это вот убрать лучше

@Tolyas · 20.04.2013, 22:40 **[ТС]**

Спасибо, все прошло, буду знать, что так можно писать в условии. Спасибо.

@UnsKneD · 20.04.2013, 23:09

Можно так

C++
1
2
3
4
5
6
7
8
9
10
    char str[] = "((123))(";
    int count = 0;
    for(int i = 0; str[i]!='\0'; i++){
        if( str[i] == '(' || str[i] == ')' ){ ++count; };
    }
    if( count%2 == 0 ) { 
        printf("1\n"); 
    } else {
        printf("0\n"); 
    };

Добавлено через 10 минут
Хотя, не всегда корректно.

Tulosba · 21.04.2013, 00:05

Сообщение от UnsKneD

Добавлено через 10 минут
Хотя, не всегда корректно.

Конечно, что тут может быть корректно если просто считать кол-во разных скобок одним счетчиком. "))"

@Olivеr · 21.04.2013, 00:28

или можно через стек (для трёх видов скобок)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
bool ChkBrackets(const string &Str)
{
    stack<char>Brackets;
 
    for (string::size_type i = 0; i != Str.size(); i++) {
        if ( (Str[i]=='(') || (Str[i]=='{') ||(Str[i]=='[') ) {
            Brackets.push(Str[i]);
        }
        else {
            switch (Str[i]) {
            case ')':
                if (!(Brackets.empty()) && (Brackets.top()=='('))
                    Brackets.pop();
                else return false;
                break;
            case '}':
                if (!(Brackets.empty()) && (Brackets.top()=='{'))
                    Brackets.pop();
                else return false;
                break;
            case ']':
                if (!(Brackets.empty()) && (Brackets.top()=='['))
                    Brackets.pop();
                else return false;
                break;
            }
        }
    }
    return Brackets.empty();
}
 
int main()
{
    string str;
    getline(cin,str);
 
    if (ChkBrackets(str))
        cout<<"OK";
    else
        cout<<"BAD";
    return 0;
}

@Tolyas · 21.04.2013, 02:33 **[ТС]**

Olivеr, Этот код не проходит по времени, но я решил эту задачу немного другим способом:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
 
using namespace std;
 
int main()
{
  int s1=0,s2=0,s3=0;
  int i1=0,i2=0,i3=0;
  int *j1,*j2,*j3;
  int n;
  cin>>n;
  char *c = new char[n];
  j1 = new int[n+1];
  j2 = new int[n+1];
  j3 = new int[n+1];
  j1[0]=-1;
  j2[0]=-1;
  j3[0]=-1;
  cin>>c;
  for(int i = 0 ;c[i]!='\0';i++)
  {
    if (c[i]=='(')
    {
      s1++;
      j1[++i1]=i;
    }
    if (c[i]==')')
    {
      s1--;
      if(j1[i1]<j2[i2]||j1[i1]<j3[i3])
      {
        s1=-1;
      }
      i1--;
 
    }
    if (c[i]=='[')
    {
      s2++;
      j2[++i2]=i;
    }
    if (c[i]==']')
    {
      s2--;
      if(j2[i2]<j1[i1]||j2[i2]<j3[i3])
      {
        s2=-1;
      }
      i2--;
    }
    if (c[i]=='{')
    {
      s3++;
      j3[++i3]=i;
    }
    if (c[i]=='}')
    {
      s3--;
      if(j3[i3]<j2[i2]||j3[i3]<j1[i1])
      {
        s3=-1;
      }
      i3--;
    }
    if ((s1<0)||(s2<0)||(s3<0))
      break;
  }
  if((s1 == 0)&&(s2 == 0)&&(s3 == 0))
    cout<<"Yes";
  else
    cout<<"No";
  return 0;
}

@Olivеr · 21.04.2013, 09:28

Tolyas,

()))))
Yes

(())
No

()
Yes

так должно быть?

@myxasa · 21.04.2013, 10:07

Olivеr, условия лучше так писать

C++
1
if( !s1 && !s2 && !s3)

на будущее)

@Tolyas · 21.04.2013, 10:53 **[ТС]**

Сообщение от Olivеr

Tolyas,
так должно быть?

Нет, так не должно быть. Так и не происходит.

@Olivеr · 21.04.2013, 11:09

myxasa, это Вы, наверное, хотели сказать Tolyas

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@Tolyas 0 / 0 / 0 Регистрация: 18.10.2011 Сообщений: 16
	20.04.2013, 22:40 [ТС]
	Спасибо, все прошло, буду знать, что так можно писать в условии. Спасибо. 0

@Olivеr 415 / 411 / 95 Регистрация: 06.10.2011 Сообщений: 832
	21.04.2013, 11:09
	myxasa, это Вы, наверное, хотели сказать Tolyas 0