洛谷 1966 libreoj 2069 火柴排队 题解

发表于 | 更新于 | 阅读次数：
本文字数： 17 字 | 阅读时长 ≈ 1 分钟

题意简述

给定两个数列，长度均为，中的数都互不相同。最小化每个数差的平方的和，形式化地，最小化:

然后输出交换次数对取膜的结果。

思路框架

显然，最优的时候就是都排好序的时候，那么我们把离散化，都看成的排列，然后算需要多少步到。是一个类似逆序对的问题，用树状数组维护即珂。

具体思路

先化简一下那个式子。把平方拆开，会发现变成三个部分：

  1. 的和
  2. 的和
  3. 的和

要让原式最小，那就要让的和最大。如何最大呢？那肯定是要排序之后一一对应。

but…Why?

只考虑的情况。设有四个数，，满足且。然后我们看看是大还是大，就珂以证出来上面那个排序了。

作差，得。由于两个都是负的，所以这个数大于。所以比大。证毕。

然后我们要求的问题就是，我们要让和一一对应，也就是的第一小对应的第一小，的第二小对应的第二小…的最大值对应的最大值。

（要解决这个问题，显然要先离散化

我们来分析一下我们的目的是啥。比如。然后我们要让中的排在第一个，中的排在第二个…中的排在第个。然后我们先处理出的反排列，设为，那么对于所有，。然后对于每个，我们令。这样，我们就把中的第个位置变成了这个位置在最优情况下应该在哪。

现在，我们的目的就变成了变换后的排列变成的最小交换次数。这就是变换后的排列的逆序对数量。树状数组维护即珂。

（上面说这么多，代码其实不长）

实现注意

  1. 交换次数要

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define mod 99999997
    #define int long long 
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    int n;
    int a[N],b[N];
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Input()
    {
        R1(n);
        F(i,1,n) R1(a[i]);
        F(i,1,n) R1(b[i]);
    }

    int lba(int x){return lower_bound(a+1,a+n+1,x)-a;}
    int lbb(int x){return lower_bound(b+1,b+n+1,x)-b;}
    int aa[N],bb[N];
    class BIT
    {
        public:
            int tree[N];
            int len;
            void BuildTree(int _len)
            {
                len=_len;
                FK(tree);
            }
            void Add(int pos,int val=1)
            {
                for(int i=pos;i<=len;i+=(i&(-i)))
                {
                    tree[i]+=val;
                }
            }
            int Query(int pos)
            {
                int ans=0;
                for(int i=pos;i>0;i-=(i&(-i)))
                {
                    ans+=tree[i];
                }
                return ans;
            }
    }T;

    int Map[N];
    void Soviet()
    {
        F(i,1,n) aa[i]=a[i],bb[i]=b[i];
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        F(i,1,n) aa[i]=lower_bound(a+1,a+n+1,aa[i])-a,bb[i]=lower_bound(b+1,b+n+1,bb[i])-b;//到此为止是离散化

        F(i,1,n) Map[aa[i]]=i;//Map: 反排列
        F(i,1,n) bb[i]=Map[bb[i]];//这之后，b[i]就变成了原本的b[i]应该出现在哪个位置才能和a对上

        //这往后，求一下bb的逆序对数量即珂。
        T.BuildTree(n);
        int ans=0;
        F(i,1,n)
        {
            ans+=T.Query(n)-T.Query(bb[i]);//维护逆序对
            ans%=mod;
            T.Add(bb[i],1);
        }
        printf("%lld\n",ans);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
    #undef int //long long 
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w