Превышен лимит времени в решении Codeforces. Как я могу улучшить свое решение?
Проблемноhttp://codeforces.com/contest/454/problem/B
Краткий обзор проблемы — данная целочисленная последовательность должна быть изменена в порядке возрастания путем применения операций сдвига (каждый элемент сдвинут на 1 позицию вправо, последний элемент становится первым). Найдите минимальное количество операций, чтобы сделать последовательность по возрастанию. Выведите -1, если это невозможно.
Я получаю TIME_LIMIT_EXCEEDED для теста 6 в приведенной выше ссылке. Я знаю, что есть более эффективные решения для этой проблемы, но если возможно, я хотел бы внести изменения в свое решение, чтобы оно работало в установленные сроки. Это будет возможно? Если да, как я могу это сделать?
Мое решение:
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
typedef long long LL;
using namespace std;
bool checkAsc(vector<int> x, int N)
{
for(int i=0;i<(N-1);i++)
{
if(x[i+1]<x[i])
return false;
}
return true;
}
vector <int> shiftRight(vector <int> &x, int N)
{
int temp=x[N-1];
for(int i=(N-1);i>=1;i--)
{
x[i]=x[i-1];
}
x[0]=temp;
vector <int> y=x;
return y;
}
bool ifPossible(vector <int> x, int N)
{
for(int i=1;i<(N-1);i++)
{
if((x[i]>x[i-1])&&(x[i]>x[i+1])&&(x[i+1]>x[i-1]))
return false;
}
return true;
}
int main()
{
int n, turns=0;
vector <int> a(100000);
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
if(!ifPossible(a, n))
cout<<"-1";
else
{
while(!checkAsc(a, n))
{
shiftRight(a, n);
turns++;
}
cout<<turns;
}
return 0;
}
Журнал проверки:
Тест: № 6, время: 1000 мс, память: 784 КБ, код выхода: -1, код выхода из проверки: 0, вердикт: TIME_LIMIT_EXCEEDED
вход
9999899997 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 74 75 76 77 78 79 80 81 82 83 84 86 86 87 88 89 90 91 93 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 15 …
Решение
Во-первых, исправьте свой алгоритм, для {3, 2, 1}, у вас есть бесконечный цикл (вместо -1).
Из вашего кода пройдите vector по const ref вместо значения, чтобы избежать ненужных копий.
ваш shiftRight может использовать vector.insert(v.back()); vector.pop_back() это та же сложность, но использовать более быстрый метод (как memcpy); и измените тип возврата на void(как результат не используется) и так откажитесь y и его копия.
Но ваш алгоритм все еще O(N²) в то время как это может быть сделано в O(N)
int get_unicorn_shift(const std::vector<int>& v)
{
auto mid = std::is_sorted_until(v.begin(), v.end());
if (mid == v.end()) {
return 0;
}
auto end = std::is_sorted_until(mid, v.end());
if (end != v.end() || v.front() < v.back()) {
return -1;
}
return end - mid;
}
Другие решения