10 Time Exceeded

foo.cc: In function 'void findSplits(int, const std::vector<int>&, std::vector<int>&, std::vector<int>&, int, int&)':
foo.cc:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
     if (index == arr.size()) {
         ~~~~~~^~~~~~~~~~~~~
# 状态 分数 耗时 内存占用
#1 Wrong Answer 0 1ms 7.7 MiB
#2 Wrong Answer 0 0ms 7.6 MiB
#3 Wrong Answer 0 1ms 7.6 MiB
#4 Wrong Answer 0 1ms 7.6 MiB
#5 Accepted 10 1ms 7.6 MiB
#6 Wrong Answer 0 359ms 7.4 MiB
#7 Wrong Answer 0 754ms 7.6 MiB
#8 Time Exceeded 0 ≥1332ms ≥7.6 MiB
#9 Time Exceeded 0 ≥1332ms ≥7.6 MiB
#10 Time Exceeded 0 ≥1333ms ≥7.7 MiB

代码

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 计算子数组的和
int sum(const vector<int>& arr) {
    int s = 0;
    for (int num : arr) {
        s += num;
    }
    return s;
}

// 使用回溯法枚举所有拆分方案
void findSplits(int index, const vector<int>& arr, vector<int>& A1, vector<int>& A2, int M, int& count) {
    if (index == arr.size()) {
        if (!A1.empty() && !A2.empty()) { // A1和A2都不能是空的
            int sumA1 = sum(A1);
            int sumA2 = sum(A2);
            if (abs(sumA1 - sumA2) == M) {
                count++;
            }
        }
        return;
    }
    
    // 将当前元素放入A1
    A1.push_back(arr[index]);
    findSplits(index + 1, arr, A1, A2, M, count);
    A1.pop_back();
    
    // 将当前元素放入A2
    A2.push_back(arr[index]);
    findSplits(index + 1, arr, A1, A2, M, count);
    A2.pop_back();
}

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<int> arr(N);
    for (int i = 0; i < N; ++i) {
        arr[i] = i + 1;
    }
    
    vector<int> A1, A2;
    int count = 0;
    
    findSplits(0, arr, A1, A2, M, count);
    
    // 输出符合条件的拆分方案数
    cout << count << endl;
    
    return 0;
}

信息

递交者
题目
LQ1098  求和比较
比赛
蓝桥杯省赛历年真题
语言
C++ 14 (O2)
递交时间
6 个月前
评测时间
6 个月前
分数
10
总耗时
≥5114ms
峰值内存
≥7.7 MiB