c++ - 有效地计算线段

Question

我正在尝试解决 Slicing Paradise来自澳大利亚信息学培训网站。这个想法是你有一系列的 block (在语句中实际上是森林，在我的代码中是 land)，并且每次一个 block 被删除(或转换为度假村)，这可能会增加或减少连续(森林) block 的运行次数。我要计算历史上最大的运行次数。输入是 block 数 N，后跟 N 行给出每个 block 的移除时间。时间是从 1 开始的连续整数。

我的代码运行良好(我认为)，但对于一些较大的案例来说太慢了。有人可以建议一个简单的快速工作解决方案，或者可以对我的进行任何改进以使其在 O(N) 中运行吗？

慢解

#include <cstdio>

FILE* infile;
FILE* outfile;
int N,c,j,l,best;

int main(){
    infile=fopen("slicein.txt","r");
    outfile=fopen("sliceout.txt","w");

    fscanf(infile,"%d\n",&N);

    int land[N+1];
    int location[N+1];

    for (int i=1;i<=N;i++){
        fscanf(infile,"%d\n",&location[i]);
        land[i]=0;
    }

    j=1;l=1;c=1;

    for (int i=1;i<=N;i++){
        if (location[i]==j){
            land[i]=1;
            if (land[i+1]!=1 && land[i-1]!=1 && i!=N && i!=1) c++;
            else if (land[i-1]==1 && land[i+1]==1 && i!=N && i!=1) c--;
            j++;
            if (c>best) best=c;
            i=0;
        }
        if (i==N && l!=N*N){
            i=0;
        }
        else if (l==N*N) break;
        l++;
    }

    fprintf(outfile,"%d\n",best);

    fclose(infile);
    fclose(outfile);

    return 0;
}

Answer 1

你的问题是你基本上有两个嵌套循环，一个用于 j 的外部循环和一个用于 i 的内部循环，尽管你没有明确地那样写。这为您提供了一种查找当前位置的 O(N) 方法，总成本为 O(N²)。

基本信息是，在每一轮j中，您需要找到在该轮中转换的位置i。您可以在读取输入时为其构建 map 。与其将 location 作为从一个位置到另一个时间的 map ，不如将它变成一个从时间到另一个位置的 map :

for (int i=1;i<=N;i++){
    int t;
    fscanf(infile,"%d\n",&t);
    location[t] = i;
    land[i]=0;
}

然后你可以凑合使用一个 O(N) 循环，一切都应该没问题。确保索引正确，因为您似乎在某些地方使用基于 1 的索引，而在其他地方使用基于 0 的索引。