P1881 绳子对折

题目描述

FJ 有一个长度为 L（1≤L≤10,000）的绳子。这个绳子上有 N（1≤N≤100）个结，包括两个端点。FJ 想将绳子对折，并使较短一边的绳子上的结与较长一边绳子上的结完全重合，如图所示：

找出FJ有多少种可行的折叠方案。

输入格式

第一行：两个整数，N 和 L。

第 2 至 N+1 行：每一行包含一个整数表示一个结所在的位置，总有两个数为 0 和 L。

输出格式

第一行： 一个整数表示FJ可折叠的方案数。

输入输出样例

输入 #1

5 10
0 
10 
6 
2 
4

输出 #1

4

说明/提示

(可在 1,2,3,8 点处折叠)

思路

标记可以折叠的方案的数量。

 完整代码

#include<bits/stdc++.h>
using namespace std;
int n,L;
bool used[20005];
bool check(int l,int r,int mid){
	while (l>=0 && r<=L){
		while (!used[l]) l--;
		while (!used[r]) r++;
		if (l>=0 && r<=L){
			if (abs(l-mid)!=abs(r-mid)) return 0;
			l--;
            r++;
		}
	}
	return 1;
}
int main(){
	cin>>n>>L;
    //freopen("a.in","r",stdin);
	L*=2;
	for (int i=1;i<=n;i++){
		int x;
		cin>>x;
		x*=2;
		used[x]=1;
	}
	
	int ans=0;
	for (int i=1;i<L;i++){
		int l=i-1,r=i+1;
		if (check(l,r,i) && i/2<L/2){
			ans++;
		} 
	}
	cout<<ans<<endl;
    //freopen("b.out","w",stdout);
	return 0;
 }