SPOJ ARRAYSUB：试着滑动窗口算法，不接受

-3

这是我实现了一个O（n）的解决方案滑动窗口对于这个问题的：SPOJ ARRAYSUB：试着滑动窗口算法，不接受

http://www.spoj.com/problems/ARRAYSUB/

#include<stdio.h> 

int i,k,n,a[1000001],q[1000001],b[1000001],m=-1; 

int main() { 
    scanf("%d",&n); 
    for(i=0;i<n;i++){ 
     scanf("%d",&a[i]); 
     if(m<a[i]) 
      m=a[i]; 
    } 
    scanf("%d",&k); 
    if(k==1){ 
     for(i=0;i<n-1;i++){ 
      printf("%d ",a[i]); 
     } 
     printf("%d",a[i]); 
    }else 
    if(k==n){ 
     printf("%d",m); 
    }else{ 
    int f=0,r=0; //front, rear 
    q[r++]=a[0]; //queue 
    for(i=1;i<n;i++){ 
     if(q[f]<=a[i]){ 
      q[f]=a[i]; //push to front, queue with single element 
      r=f+1; 
     }else{ 
      q[r++]=a[i]; //push to rear 
     } 
     if(i>=k-1){ 
      b[i-k+1]=q[f]; //write q[f] to answer array 
      if(r-f==k){ //if size of queue = k, pop first element of queue 
       f++;  
      } 
      while(q[f]<q[f+1] && f+1<r){ //after removal of first elementmove front till q[f]<q[f+1] 
       f++;   //i m not sure about this, but i tried many testcases, this works 
      } 
     } 
    } 
    for(i=0;i<n-k;i++){ 
      printf("%d ",b[i]); 
     } 
     printf("%d",b[i]); 
    } 

    return 0; 
}

然而，我找不到任何的测试用例，它不会运行，SPOJ只是不接受它:(

的代码是很好的注释。

如果任何人都可以指出一些测试用例或者，指出错误，我会很高兴！

谢谢！

来源

2015-08-14 Shivam

a）决定一个语言。 b）Spoj不明白为什么它不被接受？ c）比评论更好的是正确的缩进。 – deviantfan

我同意 - 你要么与C或C++打交道。他们完全不同，所以选择一个。你的代码在我看来像C代码。 – caps

你们是肯定苛刻，我把一个C++标签在那里，很抱歉没有意识到的不便：P – Shivam

你的周期的预期的不变量如下：队列q[f...r]的前部元件q[f]应的队列的最大元件，而队列元素的其余部分可以被存储在任何顺序。你的f更新这里

while(q[f]<q[f+1] && f+1<r){ 
    f++; 
}

没有维护不变。它找到的第一个当地最大的q[f...r]，而不变的要求全球最大。

因为这问题输入序列

5 3 2 4 1 4 4 2 5

的产生不正确的结果。对于k = 4它产生

5 3 4 4 4 5

而适当的输出是

5 4 4 4 4 5

来源

2015-08-14 23:36:59 AnT

非常感谢:) – Shivam

SPOJ ARRAYSUB：试着滑动窗口算法，不接受

回答

相关问题