计算条件为真实例的代码

Question

最近我在为即将到来的 zoc 练习时遇到 this codechef 问题。

该题要求计算给定数字的总和大于另一个给定数字的组合数。

以前我有一个蛮力算法，它给出了正确的答案但花了很多时间，在某些情况下甚至超过一秒钟，在 codechef 中引发了 TLE 错误。

所以我改变了我的整个算法以消除那个 TLE 错误，但现在它只为第一次测试提供正确答案，其余的产生错误的输出，有人可以帮我弄清楚我在这里做错了什么:

#include <iostream>
#include <vector>
int main(){
    std::vector<long long> tstCases;
    std::vector<long long> okset;
    std::vector<long long> testset;
    for(int i =0;i<2;i++){
        long long cases;
        std::cin >> cases;
        tstCases.push_back(cases);
    }
    long long n = tstCases.at(0);
    long long k = tstCases.at(1);
    for(long long i =0;i<n;i++){
        long long cases;
        std::cin >> cases;
        if(cases<=k){
            if(cases < k/2){
                okset.push_back(cases);
            }else{
                testset.push_back(cases);
            }
        }
    }
    long long l = okset.size();
    long long p1 = (l*(l-1))/2;
    long long p2 = 0;
    if(l > 0){
        for(long long i =0;i<l;i++){
            for(long long j =0;j<testset.size();j++){
                if(okset.at(i)+testset.at(j) >= k){
                    break;
                }else{
                    p2++;
                }
            }
        }
    }
    long long p = p1+p2;
    std::cout << p << std::endl;
    return 0;

}

注意：我正在使用long long，因为问题指示我这样做，而我很懒惰自己做，所以我使用了全部替换。抱歉。

Answer 1

好吧，看来我还没有对测试集数组进行排序，因此在 break 语句之后留下了很多项目。感谢 uSeemSurprised 帮助我注意到这一点。

计算条件为真实例的代码

Code for calculating instances where the condition is true

c++

algorithm

performance

vector

comparison