1237: [SCOI2008]配对
2024-09-05 18:01:39
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1789 Solved: 715
[Submit][Status][Discuss]
Description
你有n 个整数Ai和n 个整数Bi。你需要把它们配对,即每个Ai恰好对应一 个Bp[i]。要求所有配对的整数差的绝对值之和尽量小,但不允许两个相同的数配 对。例如A={5,6,8},B={5,7,8},则最优配对方案是5配8, 6配5, 8配7,配对整数 的差的绝对值分别为2, 2, 1,和为5。注意,5配5,6配7,8配8是不允许的,因 为相同的数不许配对。
Input
第一行为一个正整数n,接下来是n 行,每行两个整数Ai和Bi,保证所有 Ai各不相同,Bi也各不相同。
Output
输出一个整数,即配对整数的差的绝对值之和的最小值。如果无法配对,输 出-1。
Sample Input
3
3 65
45 10
60 25
3 65
45 10
60 25
Sample Output
32
HINT
1 <= n <= 10^5,Ai和Bi均为1到10^6之间的整数。
首先对A[i]、B[i]进行排序
在数字全部不相同的情况下,排序后的结果匹配就是最优解
一或二对数字相同,交叉匹配
三对数字相同,有两种匹配方案((1,2)(2,3)(3,1))((1,3)(2,1)(3,2))
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std; #define LL long long
const int MAXN=;
const LL INF=0x7f7f7f7f7f7f; int n;
int a[MAXN],b[MAXN];
LL f[MAXN]; LL Inc(int x,int y)
{
return a[x]==b[y]?INF:abs(a[x]-b[y]);
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
sort(a+,a+n+);sort(b+,b+n+);
f[]=Inc(,);
f[]=min(f[]+Inc(,),Inc(,)+Inc(,));
for(int i=;i<=n;i++)
{
f[i]=min(f[i-]+Inc(i,i),f[i-]+Inc(i-,i)+Inc(i,i-));
f[i]=min(f[i],f[i-]+min(Inc(i-,i-)+Inc(i-,i)+Inc(i,i-),Inc(i-,i)+Inc(i-,i-)+Inc(i,i-)));
}
if(f[n]>=INF) printf("-1");
else cout<<f[n];
return ;
}
最新文章
- html_02之表单、其它
- hdu1115(计算多边形几何重心)
- C#中virtual和abstract的区别
- 浅谈call和apply的联系&;区别&;应用匹配
- dedecms调用所有顶级栏目最新文章的实现方法
- Linux基础(4)
- python全栈阶段测试(一)
- liunx驱动----按键中断
- faster rcnn相关内容
- Cocoapods 创建自己的公开库、私有库
- cv2的安装
- 监控mysql状态脚本
- 深度学习原理与框架-卷积网络细节-经典网络架构 1.AlexNet 2.VGG
- flask 与 vue.js 2.0 实现 todo list
- K8S 使用NFS 创建PV和PVC的例子 学习From https://blog.csdn.net/xts_huangxin/article/details/51494472
- 修复 Tween.JS 的 onStop 设置无效
- 反击黑客之对网站攻击者的IP追踪
- js valueOf()函数用于返回指定对象的原始值
- Oracle PLSQL Demo - 20.弱类型REF游标[没有指定查询类型,也不指定返回类型]
- [Web Chart系列之六] canvas Chart 导出图文件
热门文章
- CRLF注入攻击
- 错误提示”void is an invalid type for the variable“
- Python 连接Sql Server数据库 MSSql
- JAVA SE collection接口
- 切图让我进步!关于white-space属性的组合拳
- Oracle数据表比较记录差异(转)
- 【起航计划 005】2015 起航计划 Android APIDemo的魔鬼步伐 04 App->;Activity->;Custom Dialog Dialog形式的Activity,Theme的使用,Shape的使用
- 初学:react-native 轮播图
- 洛谷 P2251 质量检测
- MySQL数据库实验六:存储过程建立与调用