首页 > 代码库 > BZOJ 1432: [ZJOI2009]Function(新生必做的水题)
BZOJ 1432: [ZJOI2009]Function(新生必做的水题)
1432: [ZJOI2009]Function
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1205 Solved: 895
[Submit][Status][Discuss]
Description
Input
一行两个整数n; k。
Output
一行一个整数,表示n 个函数第k 层最少能由多少段组成。
Sample Input
1 1
Sample Output
1
HINT
对于100% 的数据满足1 ≤ k ≤ n ≤ 100。
Source
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1432
分析:我们很容易知道,n条边两两相交可以截出n^2段线段(自己画画就出来了QAQ),所以对于每一层,有如下规律:
当k=1,线段数sum=n;
当k>=2时,线段数sum=(n-k+1)*2;//(推了好久才推出来的公式竟然WA了)
可惜此题叫你求出每一层最少的线段数,所以显然对前面的结论得做判定了,上面得出的线段数并非是最小值!
所以就会存在如下结论:
当n==1-->minn=1;
当n>=2-->minn=min(k,n-k+1)*2;//这个结论就是由上述推导过程加判断得出来的!QAQ
下面给出AC代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int n,k; 6 while(scanf("%d%d",&n,&k)!=EOF) 7 { 8 if(n==1) 9 cout<<1<<endl;10 else11 cout<<2*min(k,(n-k+1))<<endl;12 }13 return 0;14 }
BZOJ 1432: [ZJOI2009]Function(新生必做的水题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。