[蓝桥杯]花束搭配【算法赛】

https://www.lanqiao.cn/problems/20268/learning/?page=1&first_category_id=1&sort=students_count&asc=0&status=1&difficulty=30&tags=%E4%BA%8C%E5%88%86&tag_relation=intersection

题意

n朵花 每朵花有两个属性a,b

如果两朵花满足$a_i+a_j>b_i+b_j$ 就称为完美方案

求一共有多少种完美方案

$(i,j)与(j,i)$视为不同组合

思路

数据范围$1\le n\le 2\times 10^5$ 推测本题的做法是$O(nlogn)$

要用到排序或者优先队列

等价变形：

$$a_i+a_j>b_i+b_j\iff a_i+a_j-b_i-b_j$$

开一个d数组 记录$a_i-b_i$ 然后排序 ➕ 双指针遍历

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=2e5+10,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;
int a[N];

void solve(){
    int n;cin>>n;
    vector<int>a(n),b(n);

    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];

    vector<int>d(n);
    for(int i=0;i<n;i++) d[i]=a[i]-b[i];
    sort(d.begin(),d.end());

    int ans=0;
    int l=0,r=n-1;
    while(l<r){
        if(d[l]+d[r]>0){//此时[l,r-1]这r-l个数都能跟r组成一对 
            ans+=r-l;
            r--;
        }else l++;

    }
    cout<<(ans<<1)<<endl;//每一对可以前后互换位置 所以要乘二
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    
    int T=1;
    // cin>>T;
    while(T--) solve();
}