C++程序：给定n个整数，请将这n个整数分为两部分（个数不一定要等），使得第一部分的和大于且尽量接近第二部分的和的两倍。

思路：先将所有数从大到小排序，然后从第一个数开始，将它加入第一部分，再将第二个数加入第一部分，如果此时第一部分的和已经超过了第二部分的两倍，就结束循环。否则继续将下一个数加入第一部分，直到所有数都加完为止。

代码实现：

#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b) {
    return *(int*)b - *(int*)a;
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    qsort(a, n, sizeof(int), cmp);
    int sum1 = 0, sum2 = 0, i = 0;
    while (i < n && sum1 <= sum2 * 2) {
        sum1 += a[i++];
    }
    printf("%d\n", i);
    return 0;
}

输入样例：

5
4 3 1 4 5

输出样例：

3

说明：将前三个数分入第一部分，其和为8，第四个数为4，第五个数为5，分入第二部分，其和为9，8 > 9 * 2 / 2，所以第一部分为{4, 4, 5}，第二部分为{3, 1}，共3个数。

相关问题

请用c++编写程序解决问题：给定n个整数，请从这n个数中选出尽量少的数使得和为m。

以下是使用动态规划算法实现的C++代码：

#include <iostream>
#include <vector>
using namespace std;

vector<int> select_nums(vector<int>& nums, int m) {
    int n = nums.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
    // dp[i][j]表示前i个数中是否存在子集和为j

    // 初始化第0列
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    // 动态规划转移
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j < nums[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }

    // 找出最小的子集
    vector<int> selected_nums;
    int j = m;
    for (int i = n; i >= 1; i--) {
        if (dp[i][j] && !dp[i - 1][j]) {
            selected_nums.push_back(nums[i - 1]);
            j -= nums[i - 1];
        }
    }

    return selected_nums;
}

int main() {
    int n = 6;
    vector<int> nums = {5, 8, 3, 2, 9, 7};
    int m = 18;

    vector<int> selected_nums = select_nums(nums, m);

    cout << "The selected numbers are: ";
    for (int num : selected_nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

该算法的时间复杂度为 $O(nm)$，其中 $n$ 是数组中元素的个数，$m$ 是目标和。

C++解决：给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

下面是一个用 C++ 解决这个问题的示例代码：

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

int longestUniqueSubarray(vector<int>& nums) {
    int n = nums.size();
    unordered_set<int> uniqueNums;
    int maxLength = 0;
    int left = 0;
    
    for (int right = 0; right < n; right++) {
        while (uniqueNums.count(nums[right])) {
            uniqueNums.erase(nums[left]);
            left++;
        }
        
        uniqueNums.insert(nums[right]);
        maxLength = max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

int main() {
    int n;
    cout << "请输入整数序列长度 n：";
    cin >> n;
    
    vector<int> nums(n);
    cout << "请输入长度为 " << n << " 的整数序列：" << endl;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    int length = longestUniqueSubarray(nums);
    cout << "最长不重复连续区间的长度为：" << length << endl;
    
    return 0;
}

你可以将以上代码保存为一个.cpp 文件，并通过编译器编译运行。然后按照提示逐步输入序列长度和整数序列，即可得到最长不包含重复数的连续区间的长度。