[2017-10-06] Cow Lineup

링크 : https://www.acmicpc.net/problem/5926

1직선 상에 N개의 위치와 각 위치별 ID 값이 주어져 있는데, 모든 ID들이 최소한 하나는 포함되게 연속된 구간을 정할 때 최소 구간 길이를 구하는 문제다. 전형적인 투 포인터 문제라서 투 포인터로 슥삭하면 풀린다.

	#include <stdio.h>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <iostream>
	#include <string>
	#include <bitset>
	#include <map>
	#include <set>
	#include <tuple>
	#include <string.h>
	using namespace std;
	using i64 = long long int;
	using ii = pair<int, int>;
	using ii64 = pair<i64, i64>;
	int main()
	{
	int n;
	scanf("%d", &n);
	set<int> ids;
	vector<ii> cows(n);
	for (int i = 0; i < n; i++)
	{
	scanf("%d %d", &cows[i].first, &cows[i].second);
	ids.insert(cows[i].second);
	}
	sort(cows.begin(), cows.end());
	int minCost = 1987654321;
	int left = 0, right = 1;
	map<int, int> contains;
	contains[cows[0].second]++;
	while (right < n)
	{
	while (contains[cows[left].second] > 1)
	{
	contains[cows[left].second]--;
	if (contains[cows[left].second] == 0)
	contains.erase(cows[left].second);
	left++;
	}
	if (contains.size() == ids.size())
	{
	minCost = min(minCost, cows[right - 1].first - cows[left].first);
	}
	contains[cows[right].second]++;
	right++;
	}
	while (contains[cows[left].second] > 1)
	{
	contains[cows[left].second]--;
	if (contains[cows[left].second] == 0)
	contains.erase(cows[left].second);
	left++;
	}
	if (contains.size() == ids.size())
	{
	minCost = min(minCost, cows[right - 1].first - cows[left].first);
	}
	printf("%d", minCost);
	return 0;
	}

view raw 5926.cpp hosted with ❤ by GitHub