首页 > 试题广场 >

对比之美

[编程题]对比之美

热度指数：233 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美正在摆放她的收藏品。小美有一个漂亮的收藏架，有着一排 $n$ 个格子，从左到右分别编号为 $1 \sim n$ 。
小美打算把她的 $m$ 个收藏品放进这 $n$ 个格子中，并且尽可能的让摆放好看。怎么样才算好看呢？

小美认为有对比才有美感，相邻两个格子收藏品数量之差越大就越美。形式化地讲，

我们认为如果第 $i$ 个格子里摆放了 $a_i$ 个收藏品，那么美观度为 $\sum_{i=2}^{n}{\left| a_i - a_{i-1} \right|}$ 。

小美觉得有些格子不放收藏品也可以接受，即要求 $a_i \geq 0, \sum_{i=1}^{n}{a_i}=m$ 。请帮小美想出最美观的摆放方案！

输入描述:

第一行一个整数 $T$ 表示数据组数。

对于每组数据：

第一行2个整数分别为 $n$ 和 $m$ ，表示格子数量和收藏品数量。

对于40%的数据， $1 \leq n,m \leq 50$

对于80%的数据， $1 \leq n,m \leq 50000, 1 \leq T \leq 20$

对于100%的数据， $1 \leq n,m \leq 10^9 , 1 \leq T \leq 20$

输出描述:

输出一行 $T$ 个整数表示最大的美观度，数字间有空格隔开。

示例1

输入

输出

0 2 2

说明

对于第二组，摆放为0 2 获得美观度2

对于第三组，摆放为0 1 0 获得美观度2

可以证明没有更优方案。

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

构造基础数学滴滴

难度：

0条回答 10收藏 64浏览

热门推荐

相关试题

对比之美

扫描二维码，关注牛客网
意见反馈
下载牛客APP，随时随地刷题

扫一扫，把题目装进口袋

求职之前，先上牛客: 扫描二维码，进入QQ群



扫描二维码，关注牛客公众号

公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
牛客科技© All rights reserved admin@nowcoder.com
京ICP备14055008号-4 增值电信业务经营许可证营业执照人力资源服务许可证
京公网安备 11010502036488号