洛谷 P1638. 逛画展
原题链接
简单
作者:
y总的小迷弟
,
2023-10-01 13:47:18
,
所有人可见
,
阅读 69
//一题双解!
//法一:
//这个蒟蒻太弱,双指针写挂,只能用二分水掉这道题;
//思路就是二分门票价格mid,然后check每个长度为的mid的区间,只要符合要求就return;
//理论最坏复杂度O(nmlogn),是过不了的,但由于数据较水,加O2优化后可以通过;
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[1000010];
int st[2010];
bool isok()
{
for(int i = 1;i <= m;i++)
if(st[i] == 0)
return false;
return true;
}
bool check(int mid)
{
memset(st, 0, sizeof(st));
for(int i = 1;i <= mid;i++)
st[a[i]]++;
if(isok())
return true;
for(int i = 2;i <= n - mid + 1;i++)
{
st[a[i - 1]]--;
st[a[i + mid - 1]]++;
if(isok())
return true;
}
return false;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> a[i];
int l = 0, r = n;
while(l < r)
{
int mid = l + r >> 1;
if(check(mid))
r = mid;
else l = mid + 1;
}
memset(st, 0, sizeof(st));
for(int i = 1;i <= l;i++)
st[a[i]]++;
if(isok())
{
cout << 1 << " " << l <<endl;
return 0;
}
for(int i = 2;i <= n -l + 1;i++)
{
st[a[i - 1]]--;
st[a[i + l - 1]]++;
if(isok())
{
cout << i << " " << i +l- 1 <<endl;
return 0;
}
}
return 0;
}
//法二:双指针
#include<bits/stdc++.h>
using namespace std;
int n, m, cnt, ans = 0x3f3f3f3f, lans, rans;
int a[1000010];
int b[2010];
void insert(int x)
{
if(b[x] == 0)
cnt++;
b[x]++;
}
void remove(int x)
{
if(b[x] == 1)
cnt--;
b[x]--;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> a[i];
for(int l = 1, r = 1;r <= n;r++)
{
insert(a[r]);
while(true)
{
remove(a[l]);
if(cnt == m)
l++;
else
{
insert(a[l]);
break;
}
}
if(r - l + 1 < ans && cnt == m)
{
ans = r - l + 1;
lans = l,rans = r;
}
}
if(lans == 0)
cout << 1 << " " << n << endl;
else
cout << lans << " " << rans << endl;
return 0;
}