P1966 火柴排队

admin

https://www.luogu.org/problemnew/show/P1966

题目描述
涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为： ∑(ai-bi)^2

其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

输入输出格式
输入格式：
输入文件为 match.in。

共三行，第一行包含一个整数 n，表示每盒中火柴的数目。

第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

输出格式：
输出文件为 match.out。

输出共一行，包含一个整数，表示最少交换次数对 99,999,997 取模的结果。

输入输出样例
输入样例#1：
4
2 3 1 4
3 2 1 4
输出样例#1：
1
输入样例#2：
4
1 3 4 2
1 7 2 4
输出样例#2：
2
说明
【输入输出样例说明1】

最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。

【输入输出样例说明2】

最小距离是 10，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第 2 列中后 2 根火柴的位置。

【数据范围】

对于 10%的数据， 1 ≤ n ≤ 10；

对于 30%的数据，1 ≤ n ≤ 100；

对于 60%的数据，1 ≤ n ≤ 1,000；

对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤火柴高度≤ maxlongint

YTC

1. #include<algorithm>
   
2. using namespace std;
   
3. const int mod= 99999997;
   
4. struct node{int x;int y;};
   
5. node t1[100005],t2[100005];
   
6. int a[100005],b[100005],c[100005];
   
7. long long f[200005];
   
8. int now1,now2,n;
   
9. long long ans;
   
10. int lowbit(int x){return x&-x;}
    
11. int cmp(node a,node b){return a.x<b.x;}
    
12. long long ask(int x)
    
13. {
    
14.     long long ret=0;
    
15.     while(x>0)
    
16.     {
    
17.         ret=(ret+f[x])%mod;
    
18.         x-=lowbit(x);
    
19.     }
    
20.     return ret;
    
21. }
    
22. void add(int x,int y)
    
23. {
    
24.     while(x<=n)
    
25.     {
    
26.         f[x]+=y;
    
27.         x+=lowbit(x);
    
28.     }
    
29. }
    
30. int main()
    
31. {
    
32.     cin>>n;
    
33.     for(int i=1;i<=n;i++) {cin>>t1[i].x;t1[i].y=i;}
    
34.     sort(t1+1,t1+1+n,cmp);
    
35.     for(int i=1;i<=n;i++) {cin>>t2[i].x;t2[i].y=i;}
    
36.     sort(t2+1,t2+1+n,cmp);
    
37.     for(int i=1;i<=n;i++)
    
38.     {
    
39.         c[t1[i].y]=t2[i].y;
    
40.     }
    
41.     for(int i=n;i>=1;i--)
    
42.     {
    
43.         ans=(ans+ask(c[i]-1))%mod;
    
44.         add(c[i],1);
    
45.     }
    
46.     cout<<ans;
    
47.     return 0;
    
48. }

复制代码

关键是离散化，之后就转化成一个求逆序对的问题，可用树状数组或并归排序

倚窗倾听风吹雨

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<cstdio>
   
4. #define FOR(i,a,b) for(register int i=a;i<=b;i++)
   
5. #define ROF(i,a,b) for(register int i=a;i>=b;i--)
   
6. using namespace std;
   
7. const int N=100005,INF=99999997;
   
8. long long int n,ans,t[N],d[N];
   
9. struct node
   
10. {
    
11.     long long int num,h;
    
12. }a[N],b[N];
    
13. void Merge(long long int l,long long int r)
    
14. {
    
15.     if(l==r)return;
    
16.     long long int mid=l+((r-l)>>1);
    
17.     Merge(l,mid);
    
18.     Merge(mid+1,r);
    
19.     long long int i=l,j=mid+1,p=l;
    
20.     while(i<=mid && j<=r)
    
21.     {
    
22.         if(t[i]>t[j])
    
23.         {
    
24.             d[p++]=t[j++];
    
25.             ans+=mid-i+1;
    
26.         }
    
27.         else d[p++]=t[i++];
    
28.     }
    
29.     while(i<=mid)d[p++]=t[i++];
    
30.     while(j<=r)d[p++]=t[j++];
    
31.     FOR(i,l,r)t[i]=d[i];
    
32. 
    
33. }
    
34. inline bool cmp1(node x,node y){return x.h<y.h;}
    
35. inline bool cmp2(node x,node y){return x.num<y.num;}
    
36. int main()
    
37. {
    
38.     //freopen("testdata.in","r",stdin);
    
39.     cin>>n;
    
40.     FOR(i,1,n){cin>>a[i].h;a[i].num=i;}
    
41.     FOR(i,1,n){cin>>b[i].h;b[i].num=i;}
    
42.     sort(a+1,a+n+1,cmp1);
    
43.     sort(b+1,b+n+1,cmp1);
    
44.     FOR(i,1,n){t[a[i].num]=b[i].num;}
    
45.     Merge(1,n);
    
46.     cout<<ans%INF<<endl;
    
47.     return 0;
    
48. }
    

复制代码