cf. ConneR and the A.R.C. Markland-N

제목의 뜻은 이해하기 쉽다. 주로 n의 범위는 1e9이고 수조는 저장할 수 없다.이럴 때는 맵이나 벡터로 수조를 대신해서 역할을 발휘할 수 있다.잔말 말고 코드:맵:

#include
#include
#include
#include
using namespace std;
const int N = 1e5+10;
map<int , bool> a;
int main()
{
	int t , n , s , k;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d %d",&n,&s,&k);
		a.clear();
		while(k--)
		{
			int d;
			scanf("%d",&d);
			a[d] = 1;
		}
		if(a[s]==0)
		{
			printf("0
");
			continue;
		}
		else
		{
			int i = s , j = s;
			while(i>=1&&a[i]==1)
			{
				i--;
			}
			while(j<=n&&a[j]==1)
			{
				j++;
			}
			if(i==0)
			{
				printf("%d
",j-s);
			}
			else if(j==n+1)
			{
				printf("%d
",s-i);
			}
			else if((s-i)<=(j-s))
			{
				printf("%d
",s-i);
			}
			else
			{
				printf("%d
",j-s);
			}
			continue;
		}
	}
	return 0;
}

vector:

#include
#include
#include
#include
using namespace std;
const int N = 1e5+10;
vector<int> a;
int main()
{
	int n , k , s , t;
	cin >> t;
	while(t--)
	{
		cin >> n >> s >> k;
		a.clear();
		a.resize(k);//  a      
		for(int i = 0 ; i < k ; i++)
		{
			int d;
			cin >> d;
			a.push_back(d);
		}
		for(int i = 0 ; i <= k ; i++)
		{
			if((s-i)>=1&&find(a.begin(),a.end(),s-i)==a.end())
			{
				cout << i << endl;
				break;
			}
			if((s+i)<=n&&find(a.begin(),a.end(),s+i)==a.end())
			{
				cout << i << endl;
				break;
			}
		}
	}
	return 0;
}