刷题记录:牛客NC20650可爱の星空_“当你看向她时,有细碎星辰落入你的眼睛,真好。”——小可爱 在一个繁星闪烁的夜

传送门:牛客

题目描述:

“当你看向她时，有细碎星辰落入你的眼睛，真好。”——小可爱
在一个繁星闪烁的夜晚，卿念和清宇一起躺在郊外的草地上，仰望星空。
星语心愿，他们，想把这片星空的星星，连成一棵漂亮的树，将这美好的景色记录下来。
现在，天上共有n颗星星，编号分别为1,2.....n，一开始任何两个点之间都没有边连接。
之后，他们两个想在在(u,v)之间连无向边，需要付出|u联通块大小-v联通块大小|的代价。
他们两个想用最少的代价来使这n个点联通，所以他们想知道最小代价是多少。
(多组数据
输入:
1
5
输出:
2
1
2
3
4
5
6
7
8
9
10
11
12

emmm,感觉以前在分治题单里面做过一样的??,是一道重题??

虽然在dp的题单里,但是这个应该算作分治的一种思想吧

对于我们的一段数列,我们可以将其分成两段,然后继续的求分成两段之后每一段所需的代价(如果有人有疑问为什么分成两段是最优的,emmm,你可以自己感性的理解一下或者可以加以证明,这里不做解释),假设我们分出的两段的长度是一样的,那么此时我们不需要加一,反之加上一即可

主要的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
ll T;ll n;
ll solve(ll num) {
	if(num==1||num==2) return 0;   
	if(num&1) {
		return solve(num/2)+solve(num/2+1)+1;
	}else {
		return solve(num/2)+solve(num/2);
	}
}
int main() {
	T=read();
	while(T--) {
		n=read();
		printf("%lld\n",solve(n));
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43