当前位置: 首页> 健康> 母婴 > 【算法每日一练】新月轩就餐

【算法每日一练】新月轩就餐

时间:2025/7/11 15:08:24来源:https://blog.csdn.net/m0_69478376/article/details/139398740 浏览次数:0次

思路:

其实很容易想到是双指针或者双端队列。

我们设置一个type表示当前区间已经有了多少种厨师,同时还需要记录区间中每个元素出现的次数,然后比较棘手的是移动问题了,什么时候移动呢?

我们可以发现当区间当队头元素多余时候肯定就要移动了:

统计答案就是在type等于m的时候,只要统计l和r的位置就行了。

为什么这样的移动方式就一定可以让l和r落在最佳的答案区间上?

你可以反推:因为我们的l指向的元素一定是区间中没有多余的元素,那么如果它再右移,则区间非法;如果它不移动,也就是在l的左边,那么这个区间明显不是最佳区间。

#include <bits/stdc++.h>
using namespace std;
const int N=16+5,inf=0x3f3f3f3f;
deque<int>q;
int ans=inf;
int n,m,a[N],cnt[2001],l,r,type;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];if(!cnt[a[i]])type++;cnt[a[i]]++;q.push_back(i);//新元素进入队尾while(!q.empty()&&cnt[a[q.front()]]>1){//队头多余时候就移动cnt[a[q.front()]]--;q.pop_front();}if(type==m){//因为种类最多m,达到m时候就一直更新答案就行if(q.size()<ans){ans=q.size();l=q.front();r=q.back();}}}cout<<l<<" "<<r;
}

关键字:【算法每日一练】新月轩就餐

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: