Skip to content

1407: 分配蛋糕

题目

题目描述

你知道$n$种蛋糕,你打算为你的$m$个同学每个人购买一个蛋糕,你询问了每一个同学的意愿,他们分别告诉了你他们本人最喜欢的甜度值为$a_i$,而每种蛋糕有对应的甜度值$b_i$。每种蛋糕可以购买无数个

现在你根据每个同学的甜度值喜好,给他们买蛋糕,你希望蛋糕尽可能匹配大家的喜好。因此你希望给同学们分配的蛋糕的甜度值与同学们各自喜好的甜度值相差值的和最小。即$\Sigma|c_i-a_i|$ 最小,$c_i$为你给对应同学买的蛋糕的甜度。

于是你打算编写一个程序来求最小值是多少。

  • 注意,本题禁止使用#include<iostream>以外的所有库和头文件。

输入格式

第一行两个正整数$m$,$n$,代表蛋糕种数与同学个数且$m\ge n$。

第二行有$m$个数,代表$m$种蛋糕的甜度值。保证输入的甜度值为从小到大升序。

第三行有$n$个数,代表$n$个同学甜度值喜好。

输出格式

一个整数,代表每个人得到的蛋糕甜度值与各自的喜好相差的和最小值。

样例输入

4 3 3 6 8 10 7 4 5

样例输出

3

数据范围

对于$ 40\%$的数据,$n\le m\le 1000$。

对于另外$ 60\%$的数据,$n\le m\le 100000$。

对于所有的数据$0\le a_i,b_i\le 2^{31}-1$。

保证答案范围在$long\ long\ int$内。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!