1432: [ZJOI2009]Function

Description

Input

一行兩個整數(shù)n; k。

Output

一行一個整數(shù)，表示n 個函數(shù)第k 層最少能由多少段組成。

Sample Input

1 1

Sample Output

1

HINT

對于100% 的數(shù)據(jù)滿足1 ≤ k ≤ n ≤ 100。

---

　　很明顯這是一道結(jié)論題。又是愣沒想出來，以下來自：http://blog.csdn.net/zmoiynlp/article/details/44226459

　　n=1的時候輸出1，其余時候輸出2*k，

　　假如k>(n>>1)的話，令k=n-k+1（因為1和n-1是對稱的）。
　　為什么呢……
　　我們畫一個圖。（這個圖是很經(jīng)典的）

　　這是5條直線（函數(shù)）。可以看到，這些點以
　　A
　　BC
　　DEF
　　GHIJ
　　的方式排列。
　　第一個部分只經(jīng)過A（這樣一定是最優(yōu)的）
　　第二個部分只經(jīng)過BAC
　　第三個部分只經(jīng)過DBECF……
　　1
　　1+2
　　2+3
　　3+4……
　　線段數(shù)比點數(shù)多一，所以就是
　　2
　　4
　　6
　　8……
　　特別地，當(dāng)n=1時是1。

　　當(dāng)然，對于結(jié)論題，代碼往往都很短……

　　當(dāng)時圖已經(jīng)畫出來了，但因為題目中的“連續(xù)函數(shù)”（天知道是不是線性的），卡了很久。但現(xiàn)在一想，只有線性最優(yōu)啊……

　　我又先看了題解，罪過啊……

1 /************************************************************** 2 Problem: 1432 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:0 ms 7 Memory:820 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 int n, k, a; 13 int main() { 14 scanf("%d%d",&n,&k); 15 if(n==1) a=1; 16 else if(k<=(n>>1)) a=2*k; 17 else a=2*(n-k+1); 18 printf("%d\n",a); 19 return 0; 20 } 結(jié)論題

?

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Doggu/p/bzoj1432.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1432 [ZJOI2009]Function的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。