题解

38 条题解

  • 4
    @ 2013-11-23 11:57:50

    这道题目相当于是让我们把a,b对齐,即a中第i大的数与b中第i大的数下标相同
    一看到交换次数,很容易让人想到归并排序
    我的做法是这样的
    就样例而言:
    a:1 3 4 2
    b:1 7 2 4
    读进来之后先处理a,b 把a,b按大小离散成1..n
    离散之后
    a:1 3 4 2
    b:1 4 2 3
    那么我们现在的问题就变成了,求a转化为b所用的次数
    但是仍然很麻烦,所以要进一步离散 - -!
    我们不难看出,在a数组中,1的目的地是1。2的目的地是3。3的目的地是4.4的目的地是2
    那么我们可以另开一个数组,p[i]记录a[i]的目的地,即p={1,4,2,3}
    当a的元素全都到达目的地之后,p数组就是{1,2,3,4}
    所以答案就是使P数组变成1..n所需要的移动次数,
    之后就不需要我说了吧。。归并求逆序对还不会的可以自行百度
    由于我比较懒,所以没开p数组,直接存储在a中了,反正a也没用了
    可能我的语言表达能力不是很清楚,所以只能这样讲了
    下面贴代码
    //syc是我一个同学的名字,不要在意细节
    const
    syc=99999997;
    var
    mid,key,a,b:array[1..100000]of longint;
    u:array[1..100000]of longint;
    n,m,i,j,k:longint;ans:int64;
    procedure sort1(l,r: longint);
    var
    i,j,x,y: longint;
    begin
    i:=l;
    j:=r;
    x:=a[(l+r) div 2];
    repeat
    while a[i]<x do
    inc(i);
    while x<a[j] do
    dec(j);
    if not(i>j) then
    begin
    y:=a[i];
    a[i]:=a[j];
    a[j]:=y;
    y:=mid[i];
    mid[i]:=mid[j];
    mid[j]:=y;
    inc(i);
    j:=j-1;
    end;
    until i>j;
    if l<j then
    sort1(l,j);
    if i<r then
    sort1(i,r);
    end;
    procedure sort2(l,r: longint);
    var
    i,j,x,y: longint;
    begin
    i:=l;
    j:=r;
    x:=b[(l+r) div 2];
    repeat
    while b[i]<x do
    inc(i);
    while x<b[j] do
    dec(j);
    if not(i>j) then
    begin
    y:=b[i];
    b[i]:=b[j];
    b[j]:=y;
    y:=mid[i];
    mid[i]:=mid[j];
    mid[j]:=y;
    inc(i);
    j:=j-1;
    end;
    until i>j;
    if l<j then
    sort2(l,j);
    if i<r then
    sort2(i,r);
    end;
    procedure merge(i,j:longint);
    var
    k,p1,p2,l:longint;

    begin
    if i>=j then exit;
    l:=(i+j)div 2;
    merge(i,l);merge(l+1,j);
    p1:=i;p2:=l+1;
    for k:=i to j do
    if ((p1<=l)and(a[p1]<a[p2]))or(p2>j) then
    begin
    u[k]:=a[p1];
    inc(p1);
    end
    else
    begin
    u[k]:=a[p2];
    ans:=(ans+l-p1+1) mod syc;
    inc(p2);
    end;
    for k:=i to j do a[k]:=u[k];

    end;
    begin
    readln(n);
    for i:=1 to n do read(a[i]);
    readln;
    for j:=1 to n do read(b[j]);
    //读入,不解释
    for i:=1 to n do mid[i]:=i;
    sort1(1,n);
    for i:=1 to n do a[mid[i]]:=i;
    //把a离散化成1..n的形式
    for i:=1 to n do mid[i]:=i;
    sort2(1,n);
    for i:=1 to n do b[mid[i]]:=i;
    //把b离散化成1..n的形式
    for i:=1 to n do key[b[i]]:=i;
    for i:=1 to n do a[i]:=key[a[i]];
    //a置为a中元素的目的地
    ans:=0;
    merge(1,n);
    //归并秒杀
    writeln(ans mod syc);
    end.

  • 1
    @ 2018-06-04 22:45:31
    
    /******************
    本人思路:给出A,B两个数组
    将A中的元素和B中的元素大小一一对应
    (第i大的对应第i大的) 
    即为将离散后的A,B数组的i值通过交换
    使两个数组相等 
    
    算法:
    假设我们现在有离散化后的序列 
    a={4,3,1,2},b={1,3,2,4}。//这里为离散后的i值集合 
    我们令 q[a[i]] = b[i],
    相当于以a[i]为关键字对序列b[i] 排序。//重点!!! 
    若序列a与序列b相等,
    那么此时q[a[i]]应该等于a[i]的,也就是q[i]=i 。
    也就是说如果我们想让序列a与序列b相等,
    那么我们需要让 q 升序排列。
    问题就变为,将原本乱的q序列升序排列的最少交换次数。
    即求q数组的逆序对,可以用树状数组求解。
    ******************/
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef unsigned long long huge;
    const int num = 99999997;
    const int size = 1000005;
    struct node {
        int i; huge k;
    };
    node A[size],B[size];
    bool cmp(node a,node b) {
        return a.k < b.k;
    }
    int n,tree[2 * size];
    int lowbit(int k) {
        return k & -k;
    }
    void add(int i,int num) {
        while(i <= n) {
            tree[i] += num;
            i += lowbit(i);
        }
    }
    int Read(int i) {
        int sum = 0;
        while(i) {
            sum += tree[i];
            sum %= num;
            i -= lowbit(i);
        }
        return sum;
    }
    struct snode {
        int i,k;
    } q[size];
    bool cmp_0(snode a,snode b) {
        return a.k < b.k;
    }
    int main() {
        cin >> n;
        for(int i = 1;i <= n;i++) {
            cin >> A[i].k;
            A[i].i = i;
        }
        for(int i = 1;i <= n;i++) {
            cin >> B[i].k;
            B[i].i = i;
        }
        sort(A + 1,A + 1 + n,cmp);
        sort(B + 1,B + 1 + n,cmp);
        for(int i = 1;i <= n;i++) {
            q[A[i].i].k = B[i].i;
            q[i].i = i;
        }
        sort(q + 1,q + 1 + n,cmp_0);
        int ans = 0;
        for(int i = 1;i <= n;i++) {
            int temp = q[i].i;
            add(temp,1);
            ans += (i - Read(temp));
            ans %= num;
        }
        cout << ans << endl;
        return 0;
    }
    
  • 1
    @ 2017-10-27 17:02:44

    来一发归并排序

    #include<bits/stdc++.h>
    using namespace std;
    struct node
    {
        int h;
        int id;
    }
    ft[100010],st[100010];
    int cmp(node x,node y)
    {
        return x.h<y.h;
    }
    int s=0,n;
    int a[100010],b[100010];
    void msort(int l,int r)
    {
        if(l>=r)
        {
            return;
        }
        int mid=(l+r)>>1;
        msort(l,mid);
        msort(mid+1,r);
        int i=l;
        int k=l;
        int j=mid+1;
        while(i<=mid&&j<=r)
        {
            if(a[i]>a[j])
            {
                b[k++]=a[j++];
                s+=mid-i+1;
                s%=99999997;
            }
            else
            {
                b[k++]=a[i++];
            }
        }
        while(i<=mid)
        {
            b[k++]=a[i++];
        }
        while(j<=r)
        {
            b[k++]=a[j++];
        }
        for(int i=l;i<=r;i++)
        {
            a[i]=b[i];
        }
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&ft[i].h);
            ft[i].id=i;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&st[i].h);
            st[i].id=i;
        }
        sort(st+1,st+n+1,cmp);
        sort(ft+1,ft+n+1,cmp);
        for(int i=1;i<=n;i++)
        {
            a[ft[i].id]=st[i].id;
        }
        msort(1,n);
        printf("%d",s);
        return 0;
    }
    
  • 1
    @ 2017-10-24 15:34:34

    一脸懵逼地敲下奇奇怪怪的思路。(我真是太菜了离散化是啥???)
    要使那个式子的值最小,那就把它们排序后相同位置的数扔一起啊……这算是比较好理解的了自己算一下就好了。主要是怎么交换达到这样的数列呢?
    以样例2为例。
    q1 1 3 4 2
    q2 1 7 2 4
    看到数据我首先觉得很麻烦的是,两个序列中的数不相等,这样找对应就麻烦了很多。
    那么怎么把两个序列的数变得相等呢?可以先将两个数组排序,记下排好序后的每个位置上的数在原序列中的位置,即
    q1 1 4 2 3
    q2 1 3 4 2
    这样一来,我们就把两个序列都变成了1~n的序列。而我们要使原序列中的数大小顺序相对应,也就要使新的序列一一对应。
    但是很明显,两个序列都是乱序,排起来很麻烦,要以其中一个作为标准,把另一个排序排好。
    这时我决定用一个新的数组记录原本q1中为i的位置实际在q2中的数,即q3[q1[i]]=q2[i],此时
    q3 1 4 2 3
    而我们应该使q1和q2一一对应,即q3[i]=i。
    你看,这时是不是就是求把q3从小到大排序交换的次数了!这不就是逆序对!
    (咦?好像第一步的变化就叫离散化?
    反正我是说服我自己了。

    //老师说要用归并排序求逆序对。
    #include<cstdio>
    #include<algorithm>
    #define mo 99999997
    using namespace std;
    struct match{
        long long  l;
        int x;
    }q1[100001],q2[100001];
    int q3[100001],re[100001],s;
    int cmp(match a,match b)
    {
        if  (a.l==b.l)  return a.x<b.x;
        return a.l<b.l;
    }
    void msort(int u,int v)
    {
        if (u==v) return;
        int m=(u+v)/2,i=u,j=m+1,k=u;
        msort(u,m); msort(m+1,v);
        while (i<=m&&j<=v)
            if (q3[i]<q3[j]) re[k++]=q3[i++];
            else
            {
                re[k++]=q3[j++];
                (s+=m-i+1)%=mo;
            }
        while (i<=m) re[k++]=q3[i++];
        while (j<=v) re[k++]=q3[j++]; 
        for (i=u;i<=v;i++) q3[i]=re[i];
        return;
    }
    int main()
    {
        int n,i;
        scanf("%d",&n);
        for (i=1;i<=n;i++)
        {
            scanf("%lld",&q1[i].l);
            q1[i].x=i;
        }
        for (i=1;i<=n;i++)
        {
            scanf("%lld",&q2[i].l);
            q2[i].x=i;
        }
        sort(q1+1,q1+1+n,cmp);
        sort(q2+1,q2+1+n,cmp);
        for (i=1;i<=n;i++) q3[q1[i].x]=q2[i].x;
        msort(1,n);
        printf("%d",s);
        return 0;
    }
    

    Q:逆序对是啥?
    可以自己百度一下,就是两个数前面的大。
    Q:归并排序是啥?
    切两半切两半切两半排好一半然后合起来再排,也可以百度一下应该有板子的……
    有c++一本通第五版的可以看一下P201~204。

  • 1
    @ 2017-10-15 15:47:44

    树状数组

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #define lowbit (x & (-x))
    #define MOD 99999997
    using namespace std;
    const int N = 100000 + 10;
    
    int A[N], B[N];
    int AA[N], BB[N];
    int sot[N], temp[N];
    
    struct Tree {
        int tree[N], n;
        void modify(int x, int val) {
            while (x) {
                tree[x] += val;
                x -= lowbit;
            }
        }
        int query(int x) {
            int ans = 0;
            while (x <= n) {
                ans += tree[x];
                x += lowbit;
            }
            return ans;
        }
        void change(int l, int r, int val) {
            modify(l - 1, -val);
            modify(r, val);
        }
        void Init(int n) {
            this -> n = n;
            for (int i = 1; i <= n; i++) change(i, i, i - sot[i]);
        }
    } T;
    
    int main() {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &A[i]), temp[i] = A[i];
        sort(temp + 1, temp + n + 1);
        for (int i = 1; i <= n; i++) {
            int pos = lower_bound(temp + 1, temp + n + 1, A[i]) - temp;
            AA[i] = pos;
        }
        for (int i = 1; i <= n; i++) scanf("%d", &B[i]), temp[i] = B[i];
        sort(temp + 1, temp + n + 1);
        for (int i = 1; i <= n; i++) {
            int pos = lower_bound(temp + 1, temp + n + 1, B[i]) - temp;
            BB[pos] = i; // bb 表示在b里排行第pos的在第i位
        }
        for (int i = 1; i <= n; i++) temp[i] = BB[i];
        for (int i = 1; i <= n; i++) sot[i] = temp[AA[i]];
        for (int i = 1; i <= n; i++) temp[sot[i]] = i;
        T.Init(n);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int move = T.query(temp[i]);
            ans = (ans + abs(move)) % MOD;
            if (move > 0) T.change(1, temp[i], 1);
            else if (move < 0) T.change(temp[i], n, -1);
        }
        printf("%d", ans);
        return 0;
    }
    
  • 1
    @ 2017-07-27 09:52:17

    就是映射排序找逆序对,映射把人都搞晕了。到后面简直乱开数组乱存,竟然ac了。
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    #include<map>
    using namespace std;
    const long long mod=99999997;
    inline const void read(int &a)
    {
    a=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
    a=a*10+c-'0';
    c=getchar();
    }
    }
    int n,k,b[100001],order[100001],to[100001],a[100001];
    long long solve(int l,int r)
    {
    if(l>=r)return 0;
    int mid=(l+r)/2;
    long long ans=solve(l,mid)+solve(mid+1,r);
    int i=l,j=mid+1,temp=l;
    while(i<=mid&&j<=r)
    {
    if(b[i]>b[j]){a[temp]=b[j];j++;temp++;ans+=mid-i+1;}
    else{a[temp]=b[i];i++;temp++;}
    }
    while(i<=mid){a[temp]=b[i];i++;temp++;}
    while(j<=r){a[temp]=b[j];j++;temp++;}
    for(int i=l;i<=r;i++)b[i]=a[i];
    return ans%mod;
    }
    inline const bool compare(int i,int j)
    {
    if(b[i]<b[j])return true;
    else return false;
    }
    int main()
    {
    read(n);
    for(int i=1;i<=n;i++)
    {
    read(b[i]);
    order[i]=i;
    }
    sort(order+1,order+1+n,compare);
    for(int i=1;i<=n;i++)a[order[i]]=i;
    for(int i=1;i<=n;i++)to[a[i]]=i;
    for(int i=1;i<=n;i++)
    {
    read(b[i]);
    order[i]=i;
    }
    sort(order+1,order+1+n,compare);
    for(int i=1;i<=n;i++)b[order[i]]=to[i];
    memset(a,0,sizeof(a));
    long long ans=solve(1,n);
    printf("%d",ans%mod);
    return 0;
    }

  • 1
    @ 2015-10-29 13:57:52

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    struct asd{
    int x;
    int s;
    }a[100002],b[100002];
    int n,f[100002],ans,p[100002],k;
    int comp(asd a,asd b)
    {
    return a.s<b.s;
    }
    void fg(int h,int t)
    {
    int m,i,j;
    if(h==t) return;
    m=(h+t)/2;
    fg(h,m);
    fg(m+1,t);
    i=h; j=m+1; k=h;
    while(i<=m&&j<=t)
    {
    if(f[j]<f[i]) ans=(ans+m-i+1)%99999997;

    if(f[i]<f[j]) { p[k]=f[i]; k++; i++; }
    else { p[k]=f[j]; k++; j++; }
    }
    while(i<=m) { p[k]=f[i]; k++; i++; }
    while(j<=t) { p[k]=f[j]; k++; j++; }
    for(i=h;i<=t;i++) f[i]=p[i];
    }
    int main()
    {
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);

    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++) { scanf("%d",&a[i].s); a[i].x=i; }
    for(i=1;i<=n;i++) { scanf("%d",&b[i].s); b[i].x=i; }

    sort(a+1,a+n+1,comp);
    sort(b+1,b+n+1,comp);

    for(i=1;i<=n;i++) f[a[i].x]=b[i].x;

    fg(1,n);

    cout<<ans%99999997;

    fclose(stdin);
    fclose(stdout);

    return 0;
    }

  • 0
    @ 2018-06-15 22:10:32

    这题还是有点难度滴(其实就是近似逆序对问题)

    #include<cstdio>
    #include<algorithm>

    using namespace std;
    struct node
    {
    int a,r;
    }x[100005],y[100005];
    int A[100005],R[100005];
    bool cmp(node q,node p)
    {
    return q.a<p.a;
    }
    int ans;
    void msort(int l,int mid,int r)
    {
    int i=l,j=mid+1,k;
    for(k=l;k<=r;k++)
    {
    if((i<=mid)&&((j>r)||(A[i]<=A[j])))

    R[k]=A[i++];

    else
    {

    R[k]=A[j++];

    ans+=mid-i+1;

    }

    if(ans>=99999997) ans%=99999997;
    }
    for(i=l;i<=r;i++)

    A[i]=R[i];

    }

    void mmsort(int l,int r)

    {

    if(l<r)

    {

    int mid=(l+r)/2;

    mmsort(l,mid);

    mmsort(mid+1,r);

    msort(l,mid,r);

    }

    }
    int main()
    {
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
    scanf("%d",&x[i].a);
    x[i].r=i;
    }
    for(i=1;i<=n;i++)
    {
    scanf("%d",&y[i].a);
    y[i].r=i;
    }
    sort(x+1,x+n+1,cmp);

    sort(y+1,y+n+1,cmp);
    for(i=1;i<=n;i++)

    A[x[i].r]=y[i].r;

    mmsort(1,n);

    printf("%d\n",ans);

    return 0;
    }

  • 0
    @ 2016-11-18 20:37:23
    #include <iostream>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int maxn = 100000, mod = 99999997;
    int a[maxn], b[maxn], c[maxn], hash[maxn], ans = 0;
    void merge_sort(int c[], int d[], int start, int mid, int end) {
        int p1 = start, p2 = mid + 1, p3 = start;
        while(p1 != mid + 1 && p2 != end + 1) {
            if(c[p1] < c[p2])
                d[p3++] = c[p1++];
            else
                d[p3++] = c[p2++], ans += mid - p1 + 1, ans %= mod;
        }
        while(p1 != mid + 1)
            d[p3++] = c[p1++];
        while(p2 != end + 1)
            d[p3++] = c[p2++];
        for(int i = start; i <= end; i++)
            c[i] = d[i];
    }
    void merge(int c[], int d[], int start, int end) {
        if(start < end) {
            int mid = (start + end) / 2;
            merge(c, d, start, mid);
            merge(c, d, mid + 1, end);
            merge_sort(c, d, start, mid, end);
        }
    }
    int main() {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> a[i], hash[a[i]] = i;
        for(int i = 1; i <= n; i++)
            cin >> b[i], b[i] = hash[b[i]];
        merge(b, c, 1, n);
        cout << ans << endl;
        return 0;
    }
    

    拙劣的归并

  • 0
    @ 2016-11-15 18:31:51
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    const int maxn = 100000 + 5;
    const int MOD = 99999997;
    
    int n;
    int a[2][maxn], b[2][maxn];
    int c[maxn];
    
    int IDa (int L, int R, int &x) {
        int M = (L+R+1)/2;
        if (a[1][M] == x) return M;
        if (a[1][M] > x) return IDa(L, M-1, x);
        else return IDa(M, R, x);
    }
    
    int IDb (int L, int R, int &x) {
        int M = (L+R+1)/2;
        if (b[1][M] == x) return M;
        if (b[1][M] > x) return IDb(L, M-1, x);
        else return IDb(M, R, x);
    }
    
    inline int lowbit (int x) {
        return x&-x;
    }
    
    void add (int x) {
        while (x <= n) {
            c[x] = (c[x]+1) % MOD; x += lowbit(x);
        }
    }
    
    int sum (int x) {
        int ret = 0;
        while (x > 0) {
            ret = (ret+c[x]) % MOD; x -= lowbit(x);
        }
        return ret;
    }
    
    int main () {
    //    freopen("in.txt", "r", stdin);
        cin >> n;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[0][i]);
            a[1][i] = a[0][i];
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &b[0][i]);
            b[1][i] = b[0][i];
        }
        
        sort(a[1]+1, a[1]+n+1);
        sort(b[1]+1, b[1]+n+1);
        
        for (int i = 1; i <= n; i++) {
            a[0][i] = IDa(1, n, a[0][i]);
            c[a[0][i]] = i;
        }
        
        for (int i = 1; i <= n; i++) {
            b[0][i] = IDb(1, n, b[0][i]);
            b[0][i] = c[b[0][i]];
        }
        
        int ans = 0;
        memset(c, 0, sizeof(c));
        for (int i = n; i >= 1; i--) {
            ans = (ans + sum(b[0][i])) % MOD;
            add(b[0][i]);
        }
        cout << ans;
        
        return 0;
    }
    
  • 0
    @ 2016-11-15 14:23:00

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    const int M = 100005;
    const int MOD = 99999997;

    struct NUM{
    int x, id;
    bool operator < (const NUM& o) const{
    return x < o.x;
    }
    }bri[M];

    int a[M], b[M], to[M], c[M];
    long long ans = 0;

    void init(int n, int* s){ //离散化
    for(int i = 1; i <= n; i++)
    scanf("%d", &bri[i].x), bri[i].id = i;
    sort(bri+1, bri+1+n);
    for(int i = 1; i <= n; i++)
    s[bri[i].id] = i;
    }

    void gb(int l, int r){
    if(l == r) return;
    int mid = l + r >> 1;
    gb(l, mid);
    gb(mid + 1, r);
    int p = l, q = mid + 1, i = l;
    while(p <= mid || q <= r){
    if(q > r || (p <= mid && a[p] < a[q]))
    c[i++] = a[p++];
    else{
    if(p <= mid) ans = (ans + mid - p + 1) % MOD;
    c[i++] = a[q++];
    }
    }
    for(int i = l; i <= r; i++) a[i] = c[i];
    }

    int main()
    {
    int n;
    scanf("%d", &n);
    init(n, a);
    init(n, b);
    for(int i = 1; i <= n; i++) to[b[i]] = i;
    for(int i = 1; i <= n; i++) a[i] = to[a[i]];
    gb(1, n);
    printf("%lld", (ans + MOD) % MOD);
    return 0;
    }

  • 0
    @ 2016-10-23 18:40:59

    先把a[],b[]排序,这道题实际就是求如何用最短步数让a,b对齐,可转化为求逆序对个数

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #define MOD 99999997
    using namespace std;
    struct node{
    int x,cnt;
    }A[100005],B[100005];
    int n,s[100005],tmp[100005],ans=0;
    bool cmp(node a,node b){
    return a.x<b.x;
    }
    void merge(int l,int m,int r){
    int i=l,j=m+1,k=l;
    while(i<=m&&j<=r){
    if(s[i]>s[j]){
    tmp[k++]=s[j++];
    ans+=m-i+1;
    ans%=MOD;
    }
    else{
    tmp[k++]=s[i++];
    }
    }
    while(i<=m) tmp[k++]=s[i++];
    while(j<=r) tmp[k++]=s[j++];
    for(i=l;i<=r;i++){
    s[i]=tmp[i];
    }
    }
    void merge_sort(int l,int r){
    if(l<r){
    int m=(l+r)>>1;
    merge_sort(l,m);
    merge_sort(m+1,r);
    merge(l,m,r);
    }
    }
    int main(){
    //freopen("in.txt","r",stdin);
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
    scanf("%d",&A[i].x);
    A[i].cnt=i;
    }
    for(i=1;i<=n;i++){
    scanf("%d",&B[i].x);
    B[i].cnt=i;
    }
    sort(A+1,A+n+1,cmp);
    sort(B+1,B+n+1,cmp);
    for(i=1;i<=n;i++){
    s[A[i].cnt]=B[i].cnt;
    }
    merge_sort(1,n);
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2016-10-09 21:29:07

    嗨呀好气,这题开始都想到了,排序不等式(同序和最大)解决顺序。然后瞎想了个移动步数,WA0分......没想到要用什么逆序对..

  • 0
    @ 2016-09-21 19:28:03

    这道题的数据水到了一种境界,不取模可以得八十分,而且火柴高度都是从1到n,根本不用离散化,直接求逆序对就可以了。
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;

    const int maxn = 100000 + 10;
    const int MOD = 99999997;

    int n, ans;
    int h1[maxn], h2[maxn];
    int id[maxn];

    struct BIT {
    int C[maxn];

    inline int lowbit (int x) { return x&(-x);}

    inline void add (int x, int d) {
    while (x <= n) {
    C[x] += d; x += lowbit(x);
    }
    }

    inline int sum (int x) {
    int ret = 0;
    while (x > 0) {
    ret += C[x]; x -= lowbit(x);
    }
    return ret;
    }
    };

    BIT tree;

    int main ()
    {
    // freopen("in.txt", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h1[i];
    for (int i = 1; i <= n; i++) cin >> h2[i];
    for (int i = 1; i <= n; i++) id[h1[i]] = i;

    memset(&tree, 0, sizeof(&tree));
    ans = 0;

    for (int i = n; i >= 1; i--) {
    int cur = id[h2[i]];
    ans = (ans+tree.sum(cur))%MOD;
    tree.add(cur, 1);
    }
    cout << ans%MOD;
    return 0;
    }
    ```

  • 0
    @ 2016-08-19 20:27:27

    测试数据 #6: Accepted, time = 15 ms, mem = 3092 KiB, score = 10
    测试数据 #7: Accepted, time = 31 ms, mem = 3088 KiB, score = 10
    测试数据 #8: Accepted, time = 31 ms, mem = 3092 KiB, score = 10
    测试数据 #9: Accepted, time = 109 ms, mem = 3092 KiB, score = 10
    Accepted, time = 231 ms, mem = 3092 KiB, score = 100

    详细解答请见http://blog.csdn.net/u011325573/article/details/52245866

  • 0
    @ 2016-07-25 13:06:46

    原来是逆序对。。。我还上了个130行的treap= =

  • 0
    @ 2016-07-09 15:12:47
    /*using Binary Indexed Tree(BIT)
     *rewriting  from JDK1.8
     *21/05/2016
     */
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #define mod 99999997
    using namespace std;
    inline int read() {
        int x=0,f=1;
        char ch=getchar();
        while(ch<'0'||ch>'9') {
            if(ch=='-')f=-1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9') {
            x=(x<<1)+(x<<3)+ch-'0';
            ch=getchar();
        }
        return x*f;
    }
    int n,ans;
    int t[100005],rank[100005];
    struct data {
        int v,num;
    } a[100005],b[100005];
    inline bool cmp1(data a,data b) {
        return a.v<b.v;
    }
    inline bool cmp2(data a,data b) {
        return a.num<b.num;
    }
    inline int lowbit(int x) {
        return x&(-x);
    }
    inline int ask(int x) {
        int tmp=0;
        for(int i=x; i; i-=lowbit(i))
            tmp+=t[i];
        return tmp;
    }
    void update(int x) {
        for(int i=x; i<=n; i+=lowbit(i))
            t[i]++;
    }
    int main() {
        //freopen("data/match/match2.in","r",stdin);
        n=read();
        for(int i=1; i<=n; i++) {
            a[i].v=read();
            a[i].num=i;
        }
        for(int i=1; i<=n; i++) {
            b[i].v=read();
            b[i].num=i;
        }
        sort(a+1,a+n+1,cmp1);
        sort(b+1,b+n+1,cmp1);
        for(int i=1; i<=n; i++)
            rank[a[i].num]=b[i].num;
        sort(a+1,a+n+1,cmp2);
        for(int i=1; i<=n; i++) {
            update(rank[i]);
            ans=(ans+i-ask(rank[i]))%mod;
        }
        printf("%d",ans);
        return 0;
    }
    
  • 0
    @ 2016-07-08 15:37:52

    多谢底楼两位的题解。

    首先将求和拆开,发现ai^2+bi^2为定值,只剩下 -2*ai*bi,所以要使结果最小,则ai*bi应该要最大。
    可知当a、b两列数大小对齐时即可。求交换次数,也就是求逆序对个数。可利用归并或是线段树实现nlgn的算法。

    主要是排序后各种下标搞得很烦。。于是我开了各种数组记录的,写的有点繁琐。
    ~~~
    #include <iostream>
    #include <cstdio>
    #include <vector>
    #include <algorithm>
    #include <cstdlib>
    using namespace std;
    const int N=1000005;
    const int INF=0x3f3f3f3f;
    const int M=99999997;
    int n,ans;
    struct llh{
    int a;int b;int F;
    }p[N];
    int Fa[N],Fb[N];
    int cmpa(llh x,llh y){
    return x.a<y.a;
    }
    int cmpb(llh x,llh y){
    return x.b<y.b;
    }
    void merge(int *A,int p,int q,int r){
    int n1=q-p+1;
    int n2=r-q;
    int i,j=0,k=0;
    int *L=new int [n1+2];
    int *R=new int [n2+2];
    for(int i=p;i<=q;i++) L[j++]=A[i];
    for(int i=q+1;i<=r;i++) R[k++]=A[i];
    L[j]=R[k]=INF;
    i=p,j=k=0;
    while(L[j]!=INF&&R[k]!=INF){
    if(L[j]>R[k]){
    ans=(ans+q-(j+p)+1)%M;

    //ans+=q-j+1;
    A[i++]=R[k++];
    }
    else
    A[i++]=L[j++];
    }
    while(L[j]!=INF)
    A[i++]=L[j++];
    while(R[k]!=INF)
    A[i++]=R[k++];
    delete [] L;
    delete [] R;
    }
    void merge_sort(int *A,int p,int r){
    if(p<r){
    int q=(p+r)>>1;
    merge_sort(A,p,q);
    merge_sort(A,q+1,r);
    merge(A,p,q,r);
    }
    }
    int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&p[i].a);
    for(int i=0;i<n;i++) scanf("%d",&p[i].b);
    for(int i=0;i<n;i++) p[i].F=i;
    sort(p,p+n,cmpa);
    for(int i=0;i<n;i++) Fa[i]=p[i].F;
    sort(p,p+n,cmpb);
    for(int i=0;i<n;i++) Fb[p[i].F]=Fa[i];
    merge_sort(Fb,0,n-1);
    cout<<ans<<endl;
    return 0;
    }

    
    
  • 0
    @ 2015-10-26 21:22:57

    日了狗了,数组排来排去的好烦啊。脑子全成浆糊了。题解不写了,具体看底楼2个大牛的题解吧。
    顺便去学了树状数组和用这货求逆序对.....pascal代码不多。我就发一个,结合底下题解瞅瞅吧。

    主程序最后3个循环是求逆序对的主程序。

    ###pascal code
    program P1842;
    var a,b,c,c2:array[1..100000] of longint;
    i,ans,n,j:longint;
    function lowbit(x:longint):longint; //树状数组求管辖区间
    begin
    exit(x and (-x));
    end;

    function sum(pos:longint):longint; //计算区间内值
    begin
    sum:=0;
    while pos>0 do
    begin
    inc(sum,c2[pos]);
    dec(pos,lowbit(pos));
    end;
    end;

    procedure add(pos,x:longint); //更改树状数组的元素
    begin
    while pos<=n do
    begin
    inc(c2[pos],x);
    inc(pos,lowbit(pos));
    end;
    end;

    procedure qsort(l,r:longint);
    var i,j,mid,t:longint;
    begin
    mid:=a[(l+r) div 2]; i:=l; j:=r;
    repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if i<=j then
    begin
    t:=a[i]; a[i]:=a[j]; a[j]:=t;
    t:=c[i]; c[i]:=c[j]; c[j]:=t;
    inc(i); dec(j);
    end;
    until i>j;
    if i<r then qsort(i,r);
    if j>l then qsort(l,j);
    end;

    procedure qsort2(l,r:longint);
    var i,j,mid,t:longint;
    begin
    mid:=b[(l+r) div 2]; i:=l; j:=r;
    repeat
    while b[i]<mid do inc(i);
    while b[j]>mid do dec(j);
    if i<=j then
    begin
    t:=b[i]; b[i]:=b[j]; b[j]:=t;
    t:=c[i]; c[i]:=c[j]; c[j]:=t;
    inc(i); dec(j);
    end;
    until i>j;
    if i<r then qsort2(i,r);
    if j>l then qsort2(l,j);
    end;

    begin
    read(n); for i:=1 to n do read(a[i]); for i:=1 to n do read(b[i]);
    for i:=1 to n do c[i]:=i; qsort(1,n);
    for i:=1 to n do a[c[i]]:=i;
    for i:=1 to n do c[i]:=i; qsort2(1,n);
    for i:=1 to n do b[c[i]]:=i;
    for i:=1 to n do c[b[i]]:=i;
    for i:=1 to n do b[i]:=c[a[i]]; //要求这个数组的逆序对
    for i:=1 to n do c[i]:=i; qsort2(1,n); //找到其从大到小的顺序
    fillchar(c2,sizeof(c2),0);
    for i:=n downto 1 do //因为我快排是从小到大排的,倒着读
    begin
    add(c[i],1); ans:=(ans+sum(c[i]-1)) mod 99999997; //树状数组求逆序对
    end;

    write(ans);
    end.

信息

ID
1842
难度
6
分类
(无)
标签
递交数
4503
已通过
1099
通过率
24%
被复制
8
上传者