帮个忙,27分QwQ
  • 板块P1638 逛画展
  • 楼主lzqy_
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/4/28 11:10
  • 上次更新2023/11/7 03:47:55
查看原帖
帮个忙,27分QwQ
288716
lzqy_楼主2020/4/28 11:10

一个神奇的做法,调试得我心态爆炸。。。

好心人帮个忙吧QwQ

#include <bits/stdc++.h>
using namespace std;
int a[2000001],k[2000001];
int main()
{
  int n,m,ans=0,ans1,ans2,tail=0;
  scanf("%d%d",&m,&n);
  for(int i=1; i<=m; i++)
    scanf("%d",&a[i]),k[a[i]]++;//k是计数器
  for(int i=m; i>0; i--)//先算出左端点为1的最短区间
  {
    if(k[a[i]]==1)//如果再减就为0了
    {
      ans=i;
      ans1=1;
      ans2=i;
      tail=i;
      break;
    }
    k[a[i]]--;
  }
  for(int i=2; i<=m; i++)//计算左端点为2~m的最短区间
  {
    k[a[i-1]]--;//i-1个位置的画弹出计数器
    while(!k[a[i-1]]&&tail<=m)
    //因为只弹出了i-1这个位置,所以只用判断i-1这个位置的画还有没有
      tail++,k[a[tail]]++;
    if(!k[i-1])//如果无法满足直接跳出
      break;
    if(ans>tail-i+1)//刷新最大值
    {
      ans1=i;
      ans2=tail;
      ans=tail-i+1;
    }
  }
  cout<<ans1<<" "<<ans2;;
  return 0;
}
2020/4/28 11:10
加载中...