http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4486

从最小的开始,一个一个地往前面放就是。
怎么做?怎么快速做?
二分递归。实现细节见代码。

(只贴出与题目有关的代码,宏定义见 GitHub

/*0.479s*/
typedef pair<int, int> p2;
#define x first
#define y second

const int mx = int(1e4) + 5;

int a[mx], pos[mx], n;
vector<p2> ans;

void swap(int p, int st, int en)
{
    if (en - st == 1) return;
    if ((en - st) & 1) /// 段长为奇数,那就swap(p, st, en - 1)
    {
        --en;
        if (p == en) ans.PB(MP(p, p + 1)), --pos[a[p]], ++pos[a[p - 1]], swap(a[p - 1], a[p]), --p;
        swap(p, st, en);
        return;
    }
    if (p == st) return;
    int m = (st + en) >> 1;
    if (p < m) {swap(p, st, m); return;}
    if (p > m) swap(p, m, en);
    /// 之后p = m,交换两段
    ans.PB(MP(st + 1, en));
    int i;
    Forr(i, st, m) pos[a[i]] += m - st;
    Forr(i, m, en) pos[a[i]] -= m - st;
    rotate(a + st, a + m, a + en);
}

int solve()
{
    ans.clear();
    int i;
    Forr(i, 1, n) if (pos[i] != i - 1) swap(pos[i], i - 1, n);
    return ans.size();
}

int main()
{
    int t, i;
    SI(t);
    while (t--)
    {
        SI(n);
        SA(a, i, n), pos[a[i]] = i;
        PI(n = solve());
        For(i, n) PII(ans[i].x, ans[i].y);
    }
    return 0;
}

Comments

comments powered by Disqus