[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Форум » Компьютеры » Программирование » C++, C# » Задачка про кассы (GNU С++)
Задачка про кассы
mitrofanoffcostya2015Дата: Вторник, 17.11.2015, 19:35 | Сообщение # 1
НовичЁк
Группа: Пользователи
Сообщений: 3
Награды: 0
Репутация: 0
Статус: Оффлайн
Можно ли как-нибудь ускроить?

Код
int main()
{
    ifstream in;
    ofstream out;
    in.open("input.txt");
    out.open("output.txt");
    int n,a,b,c,d; in>>n;
    int kas[n][2], st=0, no=0;
    for (int i=0;i<n;i++)
    {
  in >> a >> b >> c >> d;
  kas[i][0]=a*60+b;
  kas[i][1]=c*60+d-1;
    }
    for (int t=0; t<1440; t++)
    {
  for (int i=0;i<n;i++)
  {
   if(kas[i][0]!=(kas[i][1]+1))
   {
    if (((kas[i][0]>kas[i][1]) && ((kas[i][0]<=t) || (t<=kas[i][1])))
    || (kas[i][0]<=t && t<=kas[i][1])) {  } else { no=1; goto hi; }
   }
  }
  hi:
  if (no == 0) { st++; } else { no = 0; }
    }
    out << st;
    in.close();
    out.close();
}


 
АлексейДата: Вторник, 17.11.2015, 21:24 | Сообщение # 2
Продвигающийся
Группа: Администраторы
Сообщений: 318
Награды: 4
Репутация: 1
Статус: Оффлайн
Код
if (((kas[i][0]>kas[1]) && ((kas[0]<=t) || (t<=kas[1])))

Поменять местами kas[0]<=t и t<=kas[1] - это даст небольшой прирост в скорости

Код
    if (((kas[0]>kas[1]) && ((kas[0]<=t) || (t<=kas[1]))) || (kas[0]<=t && t<=kas[1])) {  } else { no=1; goto hi; }

Тут можно поменять две большие части условия разделенные || , но опять же большого прироста тут не будет.

Я редко видел вокзал более, чем с 100 касс, поэтому я не думаю, что тут нужно возиться с производительностью.
 
olegsaprynovДата: Суббота, 21.11.2015, 13:36 | Сообщение # 3
НовичЁк
Группа: Пользователи
Сообщений: 5
Награды: 0
Репутация: 0
Статус: Оффлайн
Я бы на векторы разбил введённые данные и сравнивал промежутки. Тогда поиск нужных значений будет быстрее чем переживать все минуты дня.
 
АлексейДата: Среда, 16.12.2015, 01:40 | Сообщение # 4
Продвигающийся
Группа: Администраторы
Сообщений: 318
Награды: 4
Репутация: 1
Статус: Оффлайн
Ну я так понимаю добавить три лишних цикла в программу не повредит тем более за одно выполнение программы работает только один из трех циклов. В качестве минутного цикла использовал старт и конец время самой короткоработающей кассы. Сравнил по времени - ощутимо ниже - все же лучше чем сранивать все 24 часа дня, а плюс добавил конечно фишку для случая, если все кассы будут работать 24 часа. В общем код более быстрой программы ниже.
Код
int main()
{
    ifstream in;
    ofstream out;
    in.open("input.txt");
    out.open("output.txt");
    int n,a,b,c,d; in>>n;
    int kas[n][2], st=0, no=0; int min = 1440, min1 = 0, min2 = 1440;
    for (int i=0;i<n;i++)
    {
  in >> a >> b >> c >> d;
  kas[i][0]=a*60+b;
  kas[i][1]=c*60+d-1;
  if (kas[i][0]!=kas[i][1]+1)
  {
   if ( ((kas[i][1]+1)>kas[i][0]) && (((kas[i][1]+1) - kas[i][0]) < min) )
   {
    min = kas[i][1] - kas[i][0] + 1;
    min1 = kas[i][0];
    min2 = kas[i][1] + 1;
   }
   else if ( ((kas[i][1]+1)<kas[i][0]) && (( 1440 - kas[i][0] + kas[i][1] ) < min) )
   {
    min = 1440 - kas[i][0] + kas[i][1] + 1;
    min1 = kas[i][0];
    min2 = kas[i][1] + 1;
   }
  }
    }
    
    if (min2 == 1440 && min1 == 0) { st = 1440; }
    else if (min2 > min1)
    {
  for (int t=min1; t<min2; t++)
  {
   for (int i=0;i<n;i++)
   {
    if(kas[i][0]!=(kas[i][1]+1))
    {
     if (((kas[i][0]>kas[i][1]) && ((kas[i][0]<=t) || (t<=kas[i][1])))
     || (kas[i][0]<=t && t<=kas[i][1])) {} else { no=1; goto hi; }
    }
   }
   hi:
   if (no == 0) { st++; } else { no = 0; }
  }
    }
    else if (min1 > min2)
    {
  for (int t=0; t<min2;t++)
  {
   for (int i=0;i<n;i++)
   {
    if(kas[i][0]!=(kas[i][1]+1))
    {
     if (((kas[i][0]>kas[i][1]) && ((kas[i][0]<=t) || (t<=kas[i][1])))
     || (kas[i][0]<=t && t<=kas[i][1])) {} else { no=1; goto hi1; }
    }
   }
   hi1:
   if (no == 0) { st++; } else { no = 0; }
  }
  for (int t=min1; t<1440;t++)
  {
   for (int i=0;i<n;i++)
   {
    if(kas[i][0]!=(kas[i][1]+1))
    {
     if (((kas[i][0]>kas[i][1]) && ((kas[i][0]<=t) || (t<=kas[i][1])))
     || (kas[i][0]<=t && t<=kas[i][1])) {} else { no=1; goto hi2; }
    }
   }
   hi2:
   if (no == 0) { st++; } else { no = 0; }
  }
    }
    else { st = -999; }
    out << st; cout << st << endl;
    in.close();
    out.close();
}
 
valentindolgiyДата: Среда, 16.12.2015, 01:42 | Сообщение # 5
НовичЁк
Группа: Пользователи
Сообщений: 3
Награды: 0
Репутация: 0
Статус: Оффлайн
Цитата mitrofanoffcostya2015 ()
in.open("input.txt");    out.open("output.txt");

Это работа с файлами?
 
АлексейДата: Вторник, 26.01.2016, 00:08 | Сообщение # 6
Продвигающийся
Группа: Администраторы
Сообщений: 318
Награды: 4
Репутация: 1
Статус: Оффлайн
valentindolgiy, Да. Это вызовы для ввода и вывода "текста" в файл
 
Форум » Компьютеры » Программирование » C++, C# » Задачка про кассы (GNU С++)
  • Страница 1 из 1
  • 1
Поиск: