专栏文章

【1】题解：P1966 [NOIP2013 提高组] 火柴排队【树状数组】【数据结构】【逆序对】

EExFish
P1966题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqiaexl
此快照首次捕获于
2025/12/04 05:15
3 个月前
此快照最后确认于
2025/12/04 05:15
3 个月前
查看原文
题目有一个式子：∑i=1n(ai−bi)2\sum_{i=1}^n(a_i-b_i)^2。
我们拆一下，原式变为 ∑i=1nai2−2aibi+bi2\sum_{i=1}^n a_i^2-2a_ib_i+b_i^2。
再拆一次，得 ∑i=1nai2+∑i=1nbi2−2∑i=1naibi\sum_{i=1}^n a_i^2 + \sum_{i=1}^n b_i^2 - 2\sum_{i=1}^n a_ib_i。
显然，让 ∑i=1n(ai−bi)2\sum_{i=1}^n(a_i-b_i)^2 最小化，就要让 ∑i=1naibi\sum_{i=1}^n a_ib_i 最大化。
我们发现，排完序后，∑i=1naibi\sum_{i=1}^n a_ib_i 最大化。
之后逆序对即可通过。
CPP
//2022tysc0819
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;
//#define arr array<int,3>
#define int long long
//#define pb push_back
//#define double long double
//#define map unordered_map
//#pragma GCC optimize(2,3,"Ofast","inline")
const int N=2e5+10,M=1010,P=99999997,MOD=998244353;
const double PI=3.1415926,EPS=0.00001;
struct nid{int v,i;}a[N],b[N];
bool operator<(nid x,nid y){return x.v<y.v;}
int n,tr[N],su,ans,r[N];
int lb(int x){return x&-x;}
void upd(int p,int x){for(int i=p;i<=n;i+=lb(i))tr[i]+=x;}
int s(int x){su=0;for(int i=x;i>0;i-=lb(i)){su+=tr[i];}return su;}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].v,a[i].i=i;
    for(int i=1;i<=n;i++)cin>>b[i].v,b[i].i=i;
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)r[b[i].i]=a[i].i;
    for(int i=1;i<=n;i++){
        upd(r[i],1);
        ans=(ans+i-s(r[i])+P)%P;
    }
    cout<<ans;
    return 0;
}
//note:

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...