[白俊/C++230号:チョイス

ピックアップ

アイデア

二重ポインタアルゴリズムを用いた.
ダブルポインタアルゴリズム
1. start = end = 0
2.常にstart<=endを満たす.
start=0,end=0から

subがmより小さい場合はend++である.

subがmより大きい場合はstart++であり、subがansより小さい場合はans更新である.
これは、逆数の最初の数字から逆数の最初の数字を減算した場合、subよりも小さい場合はないからである.(最後から2番目以降の数字は昇順に並べられています)
1 2 3 5から
3 - 1 = 2
5–1=4.
startを座視する必要はありません.

end1 2 3 4 5
m = 1000

この場合、endは増加し続けるため、配列範囲を超えます.このような状況を避けるために

コミットコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);

	int n, m, ans = 2000000000;
	cin >> n >> m;

	vector<int> v(n);

	for (int i = 0; i < n; i++)
		cin >> v[i];

	sort(v.begin(), v.end());

	int start = 0, end = 0;

	while (start <= end && end < n)
	{
		int sub = v[end] - v[start];

		if (sub < m) // 답이 아님
			end++;
		else
		{
			ans = min(ans, sub);
			start++;
		}
	}

	cout << ans;

	return 0;
}