打卡信奥刷题（1387）用C++实现信奥 B4098 [CSP-X2022 山东] 动物园-CSDN博客

本文链接：https://blog.csdn.net/rogeliu/article/details/148201034

B4098 [CSP-X2022 山东] 动物园

题目描述

某动物园里有 $n$ 个场馆和 $m$ 种动物（ $m \leq n$ ）。

$n$ 个场馆的编号分别用 $1, 2, 3, .., n$ 表示； $m$ 种动物的编号分别用 $1, 2, 3, .., m$ 表示。每一个场馆中只饲养了一只动物，不同的场馆可能饲养着相同种类的动物。

这个动物园的门票比较特殊，游客在购买门票时必须说明要参观的场馆的起止编号 $a$ 和 $b$ （起止编号会打印到游客购买的门票上），代表游客只能参观动物园的第 $a$ 个场馆至第 $b$ 个场馆（包含 $a, b$ ）里的动物，其他的场馆不能去。门票按一个场馆十元收费。

如果你购买的门票的起止场馆编号是 $3$ 到 $8$ ，那么你需要花 $60$ 元钱购买门票，只能观看 $3, 4, 5, 6, 7, 8$ 号场馆的动物。

小明希望看到动物园内所有种类的动物，同时小明是个非常节约的孩子，他希望花最少的钱买门票。请你帮小明计算：他最少需要花费多少钱买门票才能看到所有种类的动物（同一种动物他可能不止看一个）。注意：小明只能买一张门票。

输入格式

第一行两个整数 $n, m$ ，分别表示动物园内的场馆数量及动物种类数量。

第二行是 $x_1,x_2,\cdots,x_n$ ，其中 $x_i$ 表示第 $i$ 个场馆中的动物种类编号。

输出格式

一行一个整数 $p$ ，表示小明的门票费用。

输入输出样例 #1

输入 #1

12 5
2 5 3 1 3 2 4 1 1 5 3 4 3

输出 #1

说明/提示

对于 $30\%$ 的数据，有 $ n ≤ 200 , m ≤ 20$。

对于 $60\%$ 的数据，有 $n \leq 1000, m \leq 1000$ 。

对于 $100\%$ 的数据，有 $1 ≤ n≤ 10^6，1 ≤ x_i ≤ m ≤ 2 × 10^3$ 。

C++实现

#include <bits/stdc++.h>
const int N=1e6+5,M=2e3+5;
int tong[M],a[N],n,m,l=1,r,c,mi=0x7fffffff;
signed main(){
	std::cin>>n>>m;
	for(int i=1;i<=n;i++){
		std::cin>>a[i];
	}
	while(r<=n){
		if(c<m){
			r++;
			if(!tong[a[r]])c++;
			tong[a[r]]++;
		}else{
			mi=std::min(r-l+1,mi);
			tong[a[l]]--;
			if(!tong[a[l]])c--;
			l++;
		}
	}
	std::cout<<mi*10;
	return 0;
}