The end of the school year is near and Ms. Manana, the teacher, will soon have to say goodbye to a yet another class. She decided to prepare a goodbye present for her
n students and give each of them a jigsaw puzzle (which, as wikipedia states, is a tiling puzzle that requires the assembly of numerous small, often oddly shaped, interlocking and tessellating pieces).
The shop assistant told the teacher that there are m puzzles in the shop, but they might differ in difficulty and size. Specifically, the first jigsaw puzzle consists of
f1 pieces, the second one consists of
f2 pieces and so on.
Ms. Manana doesn't want to upset the children, so she decided that the difference between the numbers of pieces in her presents must be as small as possible. Let
A be the number of pieces in the largest puzzle that the teacher buys and
B be the number of pieces in the smallest such puzzle. She wants to choose such
n puzzles that A - B is minimum possible. Help the teacher and find the least possible value of
A - B.
Output
Print a single integer — the least possible difference the teacher can obtain.
Note
Sample 1. The class has 4 students. The shop sells 6 puzzles. If Ms. Manana buys the first four puzzles consisting of 10, 12, 10 and 7 pieces correspondingly, then the difference between the sizes of the largest and the smallest puzzle will be equal to 5.
It is impossible to obtain a smaller difference. Note that the teacher can also buy puzzles 1, 3, 4 and 5 to obtain the difference 5.
题意:
我拿样例来说, 4是指人数, 6是指puzzle数
首先我们根据有多少人数, 就从puzzle中选多少个puzzle
然后在选出的puzzle中, 求出最大puzzle与最小puzzle之间的大小差~
最后, 在所有的差值中, 找最小的值
做法:
其实就是排序, 样例中可排成 22 12 10 10 7 5
我们可以看到, 排完序后, 若最大puzzle大小为22, 那么要求 最大-最小的差是最小的, 那么就选前四个22 12 10 10, 只有这样选, 最小值能保证尽量大! 从而差值小!
所以把这组数据分成 22 12 10 10 || 12 10 10 7 || 10 10 7 5 || 10 10 7 5 即可, 每组都是最大值减最小值, 再去比较那个差值最小!
AC代码:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int cmp(int a, int b) {
return a > b;
}
int main() {
int n, m;
int i, j;
int puzzle[100];
while(scanf("%d %d", &n, &m) != EOF) {
for(i = 0; i < m; i++)
scanf("%d", &puzzle[i]);
sort(puzzle, puzzle+m, cmp);
int min = 998;
for(i = 0; i <= m-n; i++)
if(puzzle[i] - puzzle[i+n-1] < min)
min = puzzle[i] - puzzle[i+n-1];
printf("%d\n", min);
}
return 0;
}
分享到:
相关推荐
安国Alcor AU6983量产工具V090409(支持34NM)
OneKeyTools10-五周年纪念最终版[SP13.08](仅支持PowerPoint) PPT好用工具
型号 额定功率(W) 稳定电压(V) 稳定电流(A) ...12.4~13.08 0.005 RLJZ3.6B O.4 3.55~3.8 0.005 RLJz6.8C 0.4 6.82~7.2 0.005 RLJZ13B 0.4 12.88~13.57 0.005 RLJZ3.
sBotClass ... 埃斯基13.08.2014güncellemesindenöncekisürümlerdewp-content / uploads / images dizini olmakzorundadır。 Dikkat(当心!) Tr:下载adverten重新下载edip onuöneçıkarılm
魔法师支票票据打印软件系统用于各类支票打印、进帐单打印、电汇凭证打印、现金交款单打印和业务委托书与业务申请书打印,帮助财务人员减轻日常票据填写工作,并有效避免填写错误。本打印软件是一款具备全自主创建...
学习使用atmega128的Boot Loader功能 实现一个世纪的boot loader程序 程序清单 ...hexbin.exe 13.08 KB main.c 7.31 KB readme.txt 451 bytes TEST.BIN 300 bytes test.hex 860 bytes
13.08.2008 AlphaControls v5.62 beta released * Improved design-time editor for the SkinManager.ThirdParty property * Fixed known errors in TsScrollBox, TsTabControl and TsPageControl components * ...
改性焦粉吸附亚甲基蓝焓变为43.33 kJ/mol,自由能变在-13.08~-8.46 kJ/mol之间,熵变在0.018~0.041 kJ/mol之间;黏附几率S=5.943×10-9,活化能为41.11 kJ/mol,表明该吸附过程是界面上混乱度增加的自发吸热过程;吸附过程...
全国支票影像交换系统架构介绍:全国支票影像交换系统(影像交换系统)是指综合运用影像技术和支付密码等技术,将纸质支票转化为影像和电子信息,实现纸质支票截留,利用信息网络...实现支票全国通用的业务处理系统。
对照组的青春期男孩(平均知识得分为15.35,标准偏差±4.748)在干预后明显高于女性(平均得分为13.08,标准偏差±4.325)(P = 0.009)。 在干预组中,干预后3个月对艾滋病毒/艾滋病有良好知识和良好态度的受访者...
开始安装6点击Finish安装完成,点击Finish7替换破解文件断网,右击桌面快捷方式→属性→打开文件位置,打开软件根目录,将破解补丁复制替换,默认目录:C:\Program Files\ACD Systems\ACDSee Pro\13.08运行注册文件...
: npm install flesch-kincaid用import { fleschKincaid } from 'flesch-kincaid'// For “The Australian platypus is seemingly a hybrid of a mammal and reptilian// creature.” (1 sentence, 13 words, 26 ...
结果表明:常温下氧浓度在13.08%时,煤样仍能够发生氧化;风量越小,氧浓度越低,CO气体浓度越高;工作面供风量减小,导致采空区出现CO气体浓度增大,停采时间越长,采空区CO气体浓度越大,但是并不能证明采空区温度有上升趋势...
结果表明:无论5月和9月,随着生长光强的降低,苦槠幼苗叶片的最大净光合速率、光补偿点和光饱和点均有减小的趋势,尤其在9月,在15%自然光强下分别为13.08Vmol・m-2・s-1,962umolm-Zs-1,198.80协mol・m-2・s-1,显著...
为探讨He-Ne激光对紫外线-B(UV-B)辐射损伤修复途径,采用He-Ne激光辐照(5 mW·mm-2)进行照射,对增强UV-B(13.08 kJ·m-2·d-1)辐射下水稻幼苗的叶绿素含量、核酮糖-1,5-二磷酸羧化酶/加氧酶(rubisco)亚基含量及反映...