NC24069. [USACO 2017 Feb P]Why Did the Cow Cross the Road
描述
Farmer John raises N breeds of cows (1≤N≤100,000), and each of his fields is dedicated to grazing for one specific breed; for example, a field dedicated to breed 12 can only be used for cows of breed 12 and not of any other breed. A long road runs through his farm. There is a sequence of N fields on one side of the road (one for each breed), and a sequence of N fields on the other side of the road (also one for each breed). When a cow crosses the road, she therefore crosses between the two fields designated for her specific breed.
Had Farmer John planned more carefully, he would have ordered the fields by breed the same way on both sides of the road, so the two fields for each breed would be directly across the road from each-other. This would have allowed cows to cross the road without any cows from different breeds bumping into one-another. Alas, the orderings on both sides of the road might be different, so Farmer John observes that there might be pairs of breeds that cross. A pair of different breeds (a,b) is "crossing" if any path across the road for breed a must intersect any path across the road for breed b.
Farmer John would like to minimize the number of crossing pairs of breeds. For logistical reasons, he figures he can move cows around on one side of the road so the fields on that side undergo a "cyclic shift". That is, for some 0≤k<N, every cow re-locates to the field k fields ahead of it, with the cows in the last k fields moving so they now populate the first k fields. For example, if the fields on one side of the road start out ordered by breed as 3, 7, 1, 2, 5, 4, 6 and undergo a cyclic shift by k=2, the new order will be 4, 6, 3, 7, 1, 2, 5. Please determine the minimum possible number of crossing pairs of breeds that can exist after an appropriate cyclic shift of the fields on one side of the road.
输入描述
The first line of input contains N. The next N lines describe the order, by breed ID, of fields on one side of the road; each breed ID is an integer in the range 1…N. The last N lines describe the order, by breed ID, of the fields on the other side of the road.
输出描述
Please output the minimum number of crossing pairs of breeds after a cyclic shift of the fields on one side of the road (either side can be shifted).
示例1
输入:
5 5 4 1 3 2 1 3 2 5 4
输出:
0
C++14(g++5.4) 解法, 执行用时: 59ms, 内存消耗: 3576K, 提交时间: 2020-07-07 14:09:13
#include <bits/stdc++.h>
using namespace std;
#define lowb(x)(x&-x)
#define fx(i, a, b) for (long long i = a; i <= b; i++)
const long long N = 100005;
long long a[N];
long long b[N];
long long bp[N];
long long ap[N];
long long c[N];
long long tree[N];
long long n;
void update(long long x,long long c){
for(;x<=n;x+=lowb(x)){
tree[x]+=c;
}
}
long long get(long long x){
long long re=0;
for(;x;x-=lowb(x)){
re+=tree[x];
}
return(re);
}
long long solve(long long *a,long long *b){
for(long long i=1;i<=n;i++){
c[b[i]]=i;
tree[i]=0;
}
long long sum=0;
long long ans=INT64_MAX;
for(long long i=1;i<=n;i++){
sum+=get(n-c[a[i]]+1);
update(n-c[a[i]]+1,1);
}
for(long long i=1;i<=n;i++){
sum-=c[a[i]]-1;
sum+=n-c[a[i]];
ans=min(ans,sum);
}
return ans;
}
int main() {
cin >> n;
fx(i, 1, n) cin >> a[i];
fx(i, 1, n) cin >> b[i];
cout << min(solve(a, b), solve(b, a));
// fx(i,1,n)cout<<b[i]<<" ";
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 38ms, 内存消耗: 2268K, 提交时间: 2019-12-29 17:42:02
#include<bits/stdc++.h>
using std::min;
#define rep(i,n) for(int i=1;i<=n;++i)
#define gc getchar()
typedef long long ll;
int read()
{
char c;
while((c=gc)<'0');
int x=c-'0';
while((c=gc)>='0')x=x*10+c-'0';
return x;
}
void chmin(ll &x,ll y)
{
if(x>y)x=y;
}
const int N=1e5+5;
int n,a[N],b[N],dy[N],q[N];
int c[N];
int qiu(int i)
{
int ans=0;
for(;i<=n;i+=i&-i)ans+=c[i];
return ans;
}
void add(int i)
{
for(;i;i-=i&-i)++c[i];
}
ll solve(int *a,int *b)
{
rep(i,n)dy[b[i]]=i;
rep(i,n)q[i]=dy[a[i]];
rep(i,n)c[i]=0;
ll ans=0;
rep(i,n)
{
ans+=qiu(q[i]);
add(q[i]);
}
ll now=ans;
for(int i=n;i;--i)
{
now-=n-q[i];
now+=q[i]-1;
chmin(ans,now);
}
return ans;
}
int main()
{
n=read();
rep(i,n)a[i]=read();
rep(i,n)b[i]=read();
printf("%lld\n",min(solve(a,b),solve(b,a)));
}