0

问题 - 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 KB，退出代码：-1，检查器退出代码：0，判断：TIME_LIMIT_EXCEEDED 输入 99998

99997 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 4 4 9 41 46 42 74 3 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 85 86 87 88 89 90 91 92 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...

4

1 回答 1

0

首先，修复你的算法，对于{3, 2, 1}，你有无限循环（而不是-1）。

从您的代码中，传递vectorconst ref 而不是 value 以避免无用的副本。您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;
}

活生生的例子

于 2014-08-02T08:27:53.867 回答