c++ - 如何在不到 1 秒的时间内运行此代码？

Question

如何在不超过时间限制的情况下解决这个问题

http://codeforces.com/problemset/problem/474/B

我尝试将所有范围放入 2D vector 中，然后使用二进制搜索查找所需的索引，但似乎 fn BS() 中的循环需要大量执行，因为 vector 可以是 10^6。

这是我的代码:

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

int Search(vector <vector<int> > a,int key){
    int start = 0;
    int end = a.size() - 1;
    while (start <= end){
        int mid = start + (end - start) / 2;
        if (a[mid][0] > key && a[mid][1] > key){
            end = mid - 1;
        }
        else if (a[mid][0] < key && a[mid][1] < key){
            start = mid + 1;
        }
        else {
            return mid;
        }
    }

    return -1;
}
vector <int> BS(vector <vector <int> > v, vector<int> keys){
    int j = 0;
    vector <int> piles;
    for (int i = 0; i < keys.size(); i++){
        piles.push_back(Search(v, keys[i])+1);
    }
    return piles;
}
vector < vector<int> > Range(vector<int> v){
    vector < vector<int> > ranges(v.size());
    int sum1 = 1;
    int sum2 = v[0];
    for (int i = 0; i < v.size(); i++){
        if (i == 0){
            ranges[i].push_back(sum1);
            ranges[i].push_back(v[i]);
            sum1 += v[i];
        }
        else{
            ranges[i].push_back(sum1);
            sum2 += v[i];
            ranges[i].push_back(sum2);
            sum1 += v[i];
        }
    }
    return ranges;
}

int main(){
    int n, m;
    cin >> n;
    vector <int> a, q;

    vector < vector <int> > v;
    for (int i = 0; i < n; i++){
        int k;
        cin >> k;
        a.push_back(k);
    }
    cin >> m;
    for (int i = 0; i < m; i++){
        int l;
        cin >> l;
        q.push_back(l);
    }

    v = Range(a);

    vector <int> jucy = BS(v, q);


    for (int i = 0; i < jucy.size(); i++){
        cout << jucy[i] << endl;
    }




}

Answer 1

事实上，我认为您根本不需要 2D vector ，您只需要 1D。例如，每个堆的上限看起来像这样 [2,9,12,16,25]，你可以很容易地构造它。然后，对于每一个多汁的蠕虫，您都以这种方式进行二进制搜索，它返回的索引值大于或等于您要查找的值。你搜索得到的索引就是你要找的那堆。

一些伪代码:

A[n] - vector of upper bounds

A[0] = a0

For each 0<i<=n A[i]=A[i-1]+ai

For each q do std lower_bound on A looking for q,

您得到的索引的第一个值等于或大于 q，因此 q 所在的堆。

和C++代码:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
    int n, m;
    cin >> n;

    vector<int>A;
    A.resize(n);

    int ai;
    cin >> ai;
    A[0]=ai;

    for (int i = 1; i < n; i++){
        cin >> ai;
        A[i]=A[i-1]+ai;
    }

    cin >> m;
    int q;
    for (int i = 0; i < m; i++){
        cin >> q;
        cout << std::distance(A.begin(),std::lower_bound(A.begin(),A.end(),q))+1<<endl;
    }

    return 0;
}

你必须给距离加上 +1，因为堆是从 1 开始编号的。为这个例子工作，看起来很快。