计算机学院大学生程序设计竞赛(2015’12)The collector’s puzzle
2024-08-29 07:33:49
Problem Description
There is a collector who own many valuable jewels. He has a problem about how to store them. There are M special boxes. Each box has a value. And each of the N jewels has a value too.
The collector wants to store every jewel in one of the boxs while minimizing the sum of difference value.
The difference value between a jewel and a box is: |a[i] - b[j]|, a[i] indicates the value of i-th jewel, b[j] indicates the value of j-th box.
Note that a box can store more than one jewel.
Now the collector turns to you for helping him to compute the minimal sum of differences.
The collector wants to store every jewel in one of the boxs while minimizing the sum of difference value.
The difference value between a jewel and a box is: |a[i] - b[j]|, a[i] indicates the value of i-th jewel, b[j] indicates the value of j-th box.
Note that a box can store more than one jewel.
Now the collector turns to you for helping him to compute the minimal sum of differences.
Input
There are multiple test cases.
For each case, the first line has two integers N, M (1<=N, M<=100000).
The second line has N integers, indicating the N jewels’ values.
The third line have M integers, indicating the M boxes’ values.
Each value is no more than 10000.
For each case, the first line has two integers N, M (1<=N, M<=100000).
The second line has N integers, indicating the N jewels’ values.
The third line have M integers, indicating the M boxes’ values.
Each value is no more than 10000.
Output
Print one integer, indicating the minimal sum of differences.
Sample Input
4 4
1 2 3 4
4 3 2 1
4 4
1 2 3 4
1 1 1 1
Sample Output
0
6
我们先排序,然后以第二个数组为基础,第一组的数据去查他们在第二组的位置
lower_bound
一共两种情况,要么刚刚好找到,一个在左边
比如
2 3 4 5 7 查找3 返回2
查找 6 返回5 我们不知道它离左边还是右边差值小,可以都考虑进去
查找8 返回最后一个位置
#include<stdio.h>
//#include<bits/stdc++.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<sstream>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<limits.h>
#define MAXN (100000+10)
#define MAXM (100000)
#define inf 0x3fffffff
#define INF 0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define ULL unsigned long long
using namespace std;
int a[MAXN],b[MAXN];
int main()
{
int n,m;
while(cin>>n>>m)
{
int sum=;
int i,j;
for(i=;i<=n;i++)
{
cin>>a[i];
}
for(i=;i<=m;i++)
{
cin>>b[i];
}
sort(a+,a+n+);
sort(b+,b+m+);
for(i=;i<=n;i++)
{
int mid=inf;
int ans=lower_bound(b+,b+m+,a[i])-b;
// cout<<ans<<endl;
if(ans<=m)
{
mid=min(mid,abs(a[i]-b[ans]));
}
if(ans>)
{
mid=min(mid,abs(a[i]-b[ans-]));
}
sum+=mid;
}
cout<<sum<<endl;
}
return ;
}
最新文章
- C# GDI+ 处理文本的两个小技巧
- Solution for Error FRM-92095: Oracle Jnitiator version too low
- Sublime Text 3065
- Microsoft Dynamics CRM 2013 --选项集的多选
- canvas ---1
- HDU 1217 Arbitrage(Floyd的应用)
- IOS开发常用的基础方法
- 在webpack里使用jquery.mCustomScrollbar插件
- (Android UI)Android应用程序中资源:图片、字符串、颜色、布局等
- (网页)javascript小技巧(非常全)
- Spark RDD 默认分区数量 - repartitions和coalesce异同
- 关于Ajax无法下载文件到浏览器本地的问题
- python --- 07 补充( join 删除和添加 fromkeys ) 深浅拷贝
- scanf_s,scanf安全版本
- 不会几个框架,都不好意思说搞过前端: Node.js &; angular.js
- MvcForum中文版+PostgreSql源码下载
- 规范抢先看!微信小程序的官方设计指南和建议
- Manifold Learning: ISOMAP
- mysql8.0.11的坑早知道
- AQTime教程