P1966
Aryper
·
·
个人记录
[NOIP2013 提高组] 火柴排队
最后调试忘记注释掉了。。。
然后我们发现 \sum_{i=1}^{n}(a_i-b_i)^2=\sum_{i=1}^na_i^2+\sum_{i=1}^nb_i^2-2\sum_{i=1}^na_ib_i ，那么使目标最小即是使 \sum_{i=1}^na_ib_i 最大。
然后我们根据某个贪心原理可以知道：
即排过序后较小的数乘上较小的数加上较大的数乘较大的数是最优的。
那么我们只要把其中一个序列中火柴按照大小顺序与另一列一一对应即可，那么排序什么的不用说，我们现在就要求使其一一对应的操作次数。
很显然相邻的逆序对交换是有效操作，而逆序对必然代表一个必须要执行的操作，那么只要求出逆序对个数就是操作次数。（讲不清楚，大概就是这样）不然当成结论记下来也差不多。。。
时间复杂度 $O(n\log n)$ 。
没了。
代码：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const ll mo=(1e8)-3,N=1e5;
struct node{
ll v,id;
bool operator < (const node &rhs) const {
return v<rhs.v;
}
}c[N+5],d[N+5];
ll n,ans;
ll a[N+5],b[N+5],tmp[N+5];
void msort(ll l,ll r) {
if(l==r) return;
ll mid=(l+r)/2;
msort(l,mid);msort(mid+1,r);
ll i=l,j=mid+1,k=l;
while(i<=mid&&j<=r) {
if(a[i]>a[j]) {
ans=(ans+mid-i+1)%mo;
tmp[k++]=a[j++];
}
else tmp[k++]=a[i++];
}
while(i<=mid) tmp[k++]=a[i++];
while(j<=r) tmp[k++]=a[j++];
for(ll i=l;i<=r;i++) a[i]=tmp[i];
}
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
return ret*f;
}
void write(ll x) {
if(x<0) {x=-x;putchar('-');}
ll y=10,len=1;
while(y<=x) {y*=10;len++;}
while(len--) {y/=10;putchar(x/y+48);x%=y;}
}
int main() {
n=read();
for(ll i=1;i<=n;i++) {
a[i]=read();c[i].v=a[i];c[i].id=i;
}
for(ll i=1;i<=n;i++) {
b[i]=read();d[i].v=b[i];d[i].id=i;
}
sort(c+1,c+n+1);sort(d+1,d+n+1);
for(ll i=1;i<=n;i++) {
a[c[i].id]=d[i].id;
}
msort(1,n);
write(ans);
return 0;
}
```