首页 > 代码库 > Codeforces Round #423 (Div. 2) D. High Load(构造题)
Codeforces Round #423 (Div. 2) D. High Load(构造题)
题目链接:Codeforces Round #423 (Div. 2) D. High Load
题意:
给你一个数n和k,让你构造出一颗树,有k个叶子节点,使得这棵树的任意两个点的距离的最大值最小。
题解:
显然要使得这棵树的任意两个点的距离的最大值最小,每个点离树根越近越好。
然后要求有k个叶子节点,所以我就任意选一个点为根,然后构成一棵m叉的树就行了。
最大距离的最小值就是离根最远的和最近的加一加就行了。
1 #include<cstdio> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 4 const int N=2e5+7; 5 int n,m,a[N]; 6 7 int main() 8 { 9 scanf("%d%d",&n,&m); 10 int now=1; 11 F(i,2,n) 12 { 13 if(i<=m+1)a[i]=1; 14 else a[i]=i-m; 15 } 16 int ans; 17 if((n-1)%m==0)ans=(n-1)/m*2; 18 else if((n-1)%m==1)ans=((n-1)/m*2)+1; 19 else ans=((n-1)/m*2)+2; 20 printf("%d\n",ans); 21 F(i,2,n)printf("%d %d\n",i,a[i]); 22 return 0; 23 }
Codeforces Round #423 (Div. 2) D. High Load(构造题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。