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

Question

如何在不超出时间限制的情况下解决此问题

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

我尝试将所有范围放在2D矢量中,然后使用二分搜索查找所需的索引,但似乎fn中的循环BS()需要花费很多时间才能执行,因为矢量的大小可以是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矢量,你只需要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.为示例工作,看起来非常快.