1015 可爱の星空 - 大连理工大学 DP·AC算法竞赛协会 ICPC集训队 Online Judge

1015: 可爱の星空

时间限制：1.000s

内存限制：128MB

提交通过: 20 提交: 58 统计

题目描述

“当你看向她时，有细碎星辰落入你的眼睛，真好。”——小可爱

在一个繁星闪烁的夜晚，卿念和清宇一起躺在郊外的草地上，仰望星空。

星语心愿，他们，想把这片星空的星星，连成一棵漂亮的树，将这美好的景色记录下来。

现在，天上共有n颗星星，编号分别为1,2.....n，一开始任何两个点之间都没有边连接。

之后，他们两个想在在(u,v)之间连无向边，需要付出|u联通块大小-v联通块大小|的代价。

他们两个想用最少的代价来使这n个点联通，所以他们想知道最小代价是多少。

(多组数据)

输入格式

第一行一个正整数，表示数据组数T

接下来T行每行一个正整数，表示询问的n

输出格式

T行，每行一个数表示答案

样例输入

1
5

样例输出

提示/说明

对于20%的数据，T<=2,n<=10

对于40%的数据，T<=10,n<=1000

对于60%的数据，T<=100000,n<=100000

对于另外40%的数据，T=1,n<=1000000000000

分类

动态规划-线性

提交