洛谷P2251 【质量检测】

无意中刷st表题看到的题目(抄模板),一看到题目,,,没想用st表,直接莫队?????跑起来也不是特别慢。。。
这里用flag数组记录出现次数,set维护最小值,用的时候直接取头部。
代码也很短

#include<bits/stdc++.h>
#define swap(a,b) {a^=b;b^=a;a^=b}
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define PII pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 1;
int n, m, mi = INF,flag[1000001], a[1000001];;
set<int>val;
int main()
{
    scanf("%d%d", &n, &m);
    rep(i, 1, n)scanf("%d", &a[i]);
    int l = 1, r = 0;
    int ll=1,rr=m;
    rep(i, 0, n - m)
    {
        while(l < ll){flag[a[l]]--;if(!flag[a[l]])val.erase(a[l]); mi = *val.begin();++l;}
        while(r < rr){++r;flag[a[r]]++;if(flag[a[r]] == 1)val.insert(a[r]);mi = *val.begin();}
        cout << mi << endl;
        ll++,rr++;
    }
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-24 13:39
在记录秋招的大魔王很...:别被忽悠了,我做了多年销售。我可以告诉你,这就是忽悠你的,销售一定要看底薪也要看提成两者不可缺一。提成是有业绩的时候才拿的到的,谁能保证一直有单状态都好。销售有时候很讲究运气的。底薪是你这个人这个岗位日常工作体现的价值。别小看底薪,你看那些跳槽去做经理主管的,底薪底一些,人家愿意去吗?所以那些说销售靠提成的纯属忽悠,除非他们的业务很容易成单。
点赞 评论 收藏
分享
牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
07-22 11:53
门头沟学院 Java
终于有一个保底的offer了,但感觉是白菜价
北凝a:我想问问,提前批的offer 有问你啥时候到岗吗,如果你还想找其他的怎么办
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务