MT3037 新月轩就餐

简介: MT3037 新月轩就餐

2edb8e3370714010894ba0897235f3c3.jpg

d49131b4b6e04f37878aec8c07263893.jpg

思路:


此题每道菜的价钱相同,想最小化付的钱即求最小区间长度可以满足“品尝到所有名厨手艺”。

使用双端队列存储元素,队尾不断向后遍历:头->尾

如果队头=队尾,则队头往右移一格,直到区间不同元素数=m。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10, M = 2005;
const int INF = 0X3f3f3f3f;
deque<int> q;
int ans = INF;
int n, m, cnt[M], a[N], 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) // 如果此时队头元素的个数大于1,就pop掉
        {
            cnt[a[q.front()]]--;
            q.pop_front();
        }
        if (type == m)
        {
            if (q.size() < ans) // 最小化付的钱
            {
                ans = q.size();
                l = q.front();
                r = q.back();
            }
        }
    }
    cout << l << " " << r << endl;
    return 0;
}


相关文章
|
12月前
|
C语言 C++ Python
在 Cython 中声明结构体、共同体、枚举
在 Cython 中声明结构体、共同体、枚举
164 0
|
运维 Kubernetes Cloud Native
云原生时代的微服务架构演进之路
随着云计算技术的不断成熟,云原生已经成为现代软件开发的重要趋势。本文将深入探讨云原生环境下微服务架构的演进过程,分析其在技术栈、部署策略、以及治理模式等方面的变化,并结合具体案例数据,展现微服务架构如何适应快速变化的市场需求和技术挑战。
|
12天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1275 5
|
2天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
11天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1291 87