下一个空格（链表c）

题目是这样的：

有N个方格的纸条，方格编号为1到N。每个方格状态为空和非空两种状态，用0或1表示。现在任务是：每次给方格位置x，问下一个（右边）空格位置在哪里？

请设计一个算法，能O(1)知道下一个位置。

【提示】

数据范围比较大，硬模拟法为O(N*M)可能会超时，可以预先处理，纪录下每个位置的下一个空格位置。就是每个格子有一个“指针”指向下一个空位置。

  第一行：2个整数N,M，范围在[2,1000000]。

  第二行：N个数字，0或1。

  第三行：M个整数，范围在[1,N]，表示要问的位置x。

 M行，每次提问后，下一个空格位置在哪里？如果后面已经没有空格，就输出-1。

输入：

7  3

1 0 0 1 1 0 1

2 4 6

输出：

3

6

-1

无

看到这个题目。枚举呀！这么简单！但是考虑一下数据范围，当然，这题没那么大，枚举是完全行的通的。不过嘛，考试会给你这么友好的数据吗？绝壁不可能，所以说，我们需要掌握一个绝对不会超时的算法。链表是一个很好地选择。链表相信大家都知道，我不多说，请看AC代码！

#include
using namespace std;
#define ll long long
int n,m,x;
ll a[100005];
int next[1000000],last;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
    last=-1;
	for(int i=n;i>=1;--i){
		next[i]=last;
		if(a[i]==0) last=i;
	}
	for(int i=1;i<=m;i++){
		scanf("%d",&x);
		printf("%dn",next[x]);
	}
	
	return 0;
}

这个方法不一定是最好的，如果谁想出了更好的方法，欢迎评论！