当前位置: 首页 > article >正文

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

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 a_i+a_j>b_i+b_j ai+aj>bi+bj 就称为完美方案

求一共有多少种完美方案

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

思路

数据范围 1 ≤ n ≤ 2 × 1 0 5 1\leq n\leq2\times10^5 1n2×105 推测本题的做法是 O ( n l o g n ) O(nlogn) O(nlogn)

要用到排序或者优先队列


等价变形:

a i + a j > b i + b j ⇔ a i + a j − b i − b j a_i+a_j>b_i+b_j \Leftrightarrow a_i+a_j-b_i-b_j ai+aj>bi+bjai+ajbibj

开一个d数组 记录 a i − b i a_i-b_i aibi 然后排序 ➕ 双指针遍历

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();
}

http://www.kler.cn/a/588513.html

相关文章:

  • python+MySQL+HTML实现产品管理系统
  • Ollama+DeepSeek+NatCross内网穿透本地部署外网访问教程
  • Flutter:竖向步骤条,类似查看物流组件
  • 一周学会Flask3 Python Web开发-SQLAlchemy更新数据操作-班级模块
  • Windows 下免安装 PostgreSQL 16、PostGIS 安装
  • Cursor插件市场打不开解决
  • CT重建笔记(四)——三维重建
  • Scheme语言的压力测试
  • 音视频缓存数学模型
  • 计算机视觉--图像数据分析基本操作
  • C# GeneticSharp包
  • 【JavaEE进阶】Spring事务
  • Linux实时内核稳定性案例
  • 精选一百道备赛蓝桥杯——5.空调
  • 鸿蒙(OpenHarmony)开发实现 息屏/亮屏 详情
  • 深度学习 Deep Learning 第1章 深度学习简介
  • 一周热点:法官在人工智能训练版权案中支持版权主张
  • SpringMVC(七)数据校验+VO++脱敏
  • DataWhale 大语言模型 - GPT和DeepSeek模型介绍
  • 弹球小游戏-简单开发版