解法一：

代码解析：

1. 核心思路：通过直径切分可以同时平分多个部分，而半径切分只能增加一个部分
2. 当总人数为偶数时，最优解是沿直径切$n/2$刀（如6人→3刀）
3. 当总人数为奇数时，必须沿半径切$n$刀（如5人→5刀）
4. 特殊情况处理：当只有1人时不需要切分

这个算法的时间复杂度是$O(1)$，空间复杂度也是$O(1)$，非常高效。通过数学分析可以证明这是最优解，因为：

• 直径切法每刀能增加最多份数
• 半径切法在无法使用直径切法时是最优选择

#include<iostream>
using namespace std;

int main(){
    int n;  // 定义变量n表示朋友数量
    cin>>n; // 输入朋友数量n
    
    n++;    // 总人数=朋友数+1（包括小枫自己）
    
    // 处理三种情况：
    if(n==1)        // 情况1：只有小枫一个人
        cout<<0;    // 不需要切分
    else if(n%2==0) // 情况2：总人数为偶数
        cout<<n/2;  // 沿直径切，每刀可平分两份
    else            // 情况3：总人数为奇数
        cout<<n;    // 必须沿半径切，每人一刀
    
    return 0;
}

解法二：

算法思路

1‌. 问题分析‌：

• 直径切法：每刀沿直径切，可以将蛋糕分成2份、4份、6份...（每次增加2份）
• 半径切法：每刀沿半径切，可以将蛋糕分成1份、2份、3份...（每次增加1份）

‌2. 关键逻辑‌：

• 首先尝试用直径切法，因为效率更高（一刀能增加2份）
• 如果总人数是偶数，可以用直径切法完美分割
• 如果总人数是奇数，必须改用半径切法（因为直径切法只能产生偶数份）

3‌. 时间复杂度‌：

• 使用while循环计算刀数，时间复杂度为$O(n$)
• 但由于n的范围是$10^5$，这个复杂度是可以接受的

4‌. 边界情况‌：

• 当$n=0$时（只有小枫自己），不需要切蛋糕
• 当$n=1$时（小枫和1个朋友），需要1刀（半径切法）

这个算法巧妙地利用了两种切法的特性，通过比较两种切法的结果，选择刀数最少的方法。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, cnt1 = 0, cnt2 = 0;  // cnt1记录直径切法刀数，cnt2记录半径切法刀数
    cin >> n;  // 输入朋友数量
    
    n++;  // 总人数 = 朋友数 + 小枫自己
    
    // 计算直径切法所需刀数
    // 直径切法：每刀沿直径切，每刀可以增加2份
    while (cnt1 * 2 < n) cnt1++;  // 找到最小的cnt1使得2*cnt1 >= n
    
    // 计算半径切法所需刀数
    // 半径切法：每刀沿半径切，每刀只能增加1份
    while (cnt2 + 1 <= n) cnt2++;  // 找到最小的cnt2使得cnt2 >= n
    
    // 特殊情况处理：只有1个人(小枫自己)时不需要切
    if (n == 1) {
        cout << 0;
        return 0;
    }
    // 如果直径切法能正好分成n份(即n是偶数)
    else if (cnt1 * 2 == n) {
        cout << cnt1;  // 输出直径切法的刀数
    }
    // 否则使用半径切法
    else {
        cout << cnt2;  // 输出半径切法的刀数
    }
    
    return 0;
}