#题解#洛谷 P3029 Cow Lineup S #双指针#离散化#

P3029 [USACO11NOV] Cow Lineup S - 洛谷

分析

1. 离散化，双指针

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
struct cow
{int pos, x;
} a[N];
bool cmp(cow x, cow y)
{return x.pos < y.pos;
}
map<int, int >m;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i].pos >> a[i].x;m[a[i].x] = 0;}int kind = m.size();sort(a + 1, a + 1 + n, cmp);
//	for(int i=1;i<=n;i++)
//		cout<<a[i].x<<" "<<a[i].pos<<'\n';int cnt = 0;int min_cost = 1e9;int j = 1;for (int i = 1; i <= n; i++){while (cnt < kind && j <= n){if (m[a[j].x] == 0)cnt++;m[a[j].x]++;j++;}if (kind == cnt)min_cost = min(min_cost, a[j - 1].pos - a[i].pos);m[a[i].x]--;if (m[a[i].x] == 0)cnt--;}cout << min_cost;return 0;
}