38 条题解
-
4
skydec LV 8 @ 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
/****************** 本人思路：给出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
2351599120 LV 9 @ 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
一脸懵逼地敲下奇奇怪怪的思路。（我真是太菜了离散化是啥？？？）
要使那个式子的值最小，那就把它们排序后相同位置的数扔一起啊……这算是比较好理解的了自己算一下就好了。主要是怎么交换达到这样的数列呢？
以样例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
树状数组
#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
就是映射排序找逆序对，映射把人都搞晕了。到后面简直乱开数组乱存，竟然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
#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
2501953407 LV 8 @ 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
invincible_ryz LV 8 @ 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
#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
#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
-
0
先把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
caesar_199 LV 9 @ 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
测试数据 #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
/*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
tootal (hzq) LV 9 @ 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
日了狗了，数组排来排去的好烦啊。脑子全成浆糊了。题解不写了，具体看底楼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.
skydec
LV 8
@ 2013-11-23 11:57:50
信息
- ID
- 1842
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 5085
- 已通过
- 1102
- 通过率
- 22%
- 被复制
- 10
- 上传者
-
Towerlight
