• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

P7629 [COCI2011-2012#1] SORT 题解

开发技术 开发技术 6小时前 2次浏览

sort

这题题意就是给定有 (n) 个数的数组 (a),每次将 (a) 划分为多个连续的下降区间,将每个有至少两个数的区间翻转。问让 (a) 排好序需要至少多少次翻转。

(O(n^2)) 的做法很显然,就按题意模拟即可,考虑优化

假设第一次数组 (a) 划分成了 ([1,2,dots,p_1],[p_1+1,p_1+2,dots,p2],dots,[p_{s-1}+1,p_{s-2}+1,…,p_s](p_s=n)),那么做完第一次轮反转操作后,每一个区间都是按从小到大排好序的。那么做第二轮操作时,下降区间就只能跨越第一轮的相邻区间。比如说:4 2 3 1,第一轮为 4 2 | 3 1,翻转之后变成了 2 4 | 1 3,第二次下降区间只有 4 1。然后有个显而易见的结论就是第二次以后的下降区间长度只能为 (2)

那么问题就转换为了每次交换相邻的数,问排好序之后的最小交换次数。然后逆序对做就行了。

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5 + 5;

int n;
LL ans;
int a[N], cut[N];

class BIT {
  public:
    void upd (int x, int v) {
      for (; x <= n; x += x & -x)
        c[x] += v;
    }
    LL qry (int x) {
      LL ret = 0;
      for (; x; x -= x & -x)
        ret += c[x];
      return ret; 
    }
  private:
    LL c[N];
} t ;

bool check () {
  for (int i = 1; i <= n; ++i)
    if (a[i] != i) return false;
  return true;
}

void solve () {
  int cnt = 0;
  for (int i = 1; i <= n; ++i)
    if (a[i] < a[i + 1])
      cut[++cnt] = i;
  for (int i = 1; i <= cnt; ++i)
    if (cut[i] - cut[i - 1] != 1) {
      reverse(a + cut[i - 1] + 1, a + cut[i] + 1);
      ++ans;
    }
  for (int i = 1; i <= n; ++i) {
    ans += i - 1 - t.qry(a[i]);
    t.upd(a[i], 1);
  }
  cout << ans << endl;
}

int main() {
  // freopen("sort.in", "r", stdin);
  // freopen("sort.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> a[i];
  a[n + 1] = n + 1;
  solve();
  cerr << clock() * 1.0 / CLOCKS_PER_SEC << 's' << endl;
  return 0;
}

程序员灯塔
转载请注明原文链接:P7629 [COCI2011-2012#1] SORT 题解
喜欢 (0)