华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1061|回复: 0
打印 上一主题 下一主题

P1103 书本整理

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-9-28 16:45:52 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
https://www.luogu.org/problemnew/show/P1103

题目描述
Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架,想要把书放在书架上。书架可以放下所有的书,所以Frank首先将书按高度顺序排列在书架上。但是Frank发现,由于很多书的宽度不同,所以书看起来还是非常不整齐。于是他决定从中拿掉k本书,使得书架可以看起来整齐一点。

书架的不整齐度是这样定义的:每两本书宽度的差的绝对值的和。例如有4本书:

1×2
5×3
2×4
3×1
那么Frank将其排列整齐后是:

1×2
2×4
3×1
5×3
不整齐度就是2+3+2=7
已知每本书的高度都不一样,请你求出去掉k本书后的最小的不整齐度。

输入输出格式
输入格式:
第一行两个数字n和k,代表书有几本,从中去掉几本。(1≤n≤100,1≤k<n)

下面的n行,每行两个数字表示一本书的高度和宽度,均小于200。

保证高度不重复

输出格式:
一行一个整数,表示书架的最小不整齐度。

输入输出样例
输入样例#1:
4 1
1 2
2 4
3 1
5 3
输出样例#1:
3
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 01:50 , Processed in 0.466566 second(s), 26 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表