1、交换完全二叉树某子树
        第一眼看上去需要建立二叉树，但是因为是完全二叉树，可以直接用数组代替，对于每个节点n，其子树为2n和2n+1，因此直接根据这个规律操作数组即可。
        因为对于节点n，其子树也需要交换，因此这里采用递归，对节点n的子树及其子树节点也进行交换。
        对于节点n，首先判断其左右子树是否存在，如果不存在，直接返回；如果存在，则对左右子树进行递归，最后左右子树全部交换完后，再对当前节点的左右子树进行交换。 

#include<iostream>
#include<vector>

using namespace std;

void dfs(vector<int> &arr, int left, int right)
{
	if (left > arr.size() - 1 || right > arr.size() - 1)
		return;
	else
	{
		dfs(arr, 2 * left+1, 2 * right+1);
		dfs(arr, 2 * (left + 1), 2 * (right + 1));
		swap(arr[left], arr[right]);
		return;
	}
}

int main()
{
	vector<int> arr = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
	int n = 3;
	dfs(arr, 2 * n-1, 2 * n);

	for (int i = 0; i < arr.size(); i++)
		cout << arr[i] << " ";
	cout << endl;

	system("pause");
	return 0;
}



2、有N种商品，每种商品有N_i个，现在需要将K个不同的商品放入福袋中，问最多可以做多少个福袋
        我的思路是，尽可能先拿个数多的那种商品。
        首先将个数最多的K个商品，每种中拿出1个，然后对剩余的个数进行排序，再从个数最多的K个中每种拿出一个...每次拿之前先判断剩余商品种类是否大于K个。
int main()
{
    int N, K;
    cin >> N >> K;
    vectorarr(N, 0);
    for(int i = 0; i< N; i++)
        cin >> arr[i];
    int flag = 0;
    int res = 0;
    while(1)
    {
        flag = 0;
        for(int i = 0; i< N; i++)
            if(arr[i] > 0)
                flag++;
        if(flag < K)
            break;

        sort(arr.begin(), arr.end());

        for(int i = arr.size()-1; i >= arr.size()-K; i--)
            arr[i]--;

        res++;
    }

    cout << res << endl;

    return 0 ;
}




3、老王打字：①输入一个字母，步数加1；选定全部已输入字符，步数加2；复制全部选定字符，步数加2；粘贴全部复制字符，步数加2；按ESC取消选择，步数加1；

问：输入N个字最少需要多少步。
动态规划：

    假设F(n)表示输入n个字需要的步数。
    F(0) = 0；
    F(1) = 1;
    F(2) ：分情况讨论：①在输入了1个字的基础上，再输入1个字，即F(2) = F(2-1) + 1；②第二、三种情况，这里不明显，后面讨论
    F(3) ：分情况讨论：①在输入1个的基础上输入2个，在输入2个的基础上输入1个，即F(3) = min( F(3-2) + 2,  F(3 - 1) + 1)，两种情况中取最小值；②第二、三种情况，这里还是不明显，下一步讨论
    ........
    F(10) ：分情况讨论：
    ①即为上面，在输入了i个字符的基础上，再输入10-i个，(i为从1到9)；
    ②第二种情况：输入了i个字符后，我复制这i个字符，取消选择，然后在后面进行多次粘贴，这里的i可以从1到10/2；循环取i，求最小值，需要注意的是，当10%i不为0时，需要再加上F(10%i)；
    ③第三种情况：输入了i个字符后，我还是复制粘贴这i个字符，但是上面②是复制之后，取消选择，在原来的后面继续粘贴；这里我复制之后，输入一个字符，将原来输入的都覆盖掉，然后再粘贴；


int main()
{
    int N;
    cin >> N;
    vectordp(N+1, 99999);
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2; i <= N; i++)
    {
        for(int j = 1; j <= i; j++)
            dp[i] = min(dp[i], dp[i-j] + j); //情况①
        for(int j = 1; j <= i/2; j++)
        {
            dp[i] = min(dp[i], dp[j] + i/j*2 + 3 + dp[i%j]); //情况②
            dp[i] = min(dp[i], dp[j] + i/j*2 + 5); //情况③
        }
    }

    cout << dp[N] << endl;

    return 0;
}