欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

好吃的巧克力题解

程序员文章站 2022-03-10 16:54:20
题目描述 超市正在特价售卖巧克力,正好被贪吃的 Lucky_dog 看见了。 巧克力从左到右排成一排,一共有 N 个,M 种。 超市有一个很奇怪的规定,就是你在购买巧克力时必须提供两个数字 a 和 b,代表你要购买第 a 个至第 b 个巧克力(包含 a 和 b)之间的所有巧克力。 假设所有巧克力的单 ......

题目描述

超市正在特价售卖巧克力,正好被贪吃的 lucky_dog 看见了。
巧克力从左到右排成一排,一共有 n 个,m 种。
超市有一个很奇怪的规定,就是你在购买巧克力时必须提供两个数字 a 和 b,代表你要购买第 a 个至第 b 个巧克力(包含 a 和 b)之间的所有巧克力。
假设所有巧克力的单价均为 1 元。lucky_dog 想吃所有种类的巧克力,但又想省钱。作为 lucky_dog 的朋友,他请你来帮他决定如何选择购买巧克力时的 a 和 b。

输入格式:
第一行包含两个正整数 n 和 m,分别代表巧克力的总数及种类数。
第二行包含 n 个整数,这些整数均在1 至 m 之间,代表对应的巧克力所属的种类。

输出格式:
输出仅一行,包含两个整数 a 和 b,由一个空格隔开,表示花费最少且包含所有种类巧克力的购买区间。
数据保证有解,如果存在多个符合条件的购买区间,输出 a 最小的那个。

解题思路

1.选定头部后,每出现一种新的种类,计数器加一
2.当头部种类出现两次,头部右移一位
贪心算法的思想:如果头部种类出现两次,那么肯定不是最优解,至少头部右端更优
3.满足条件,更新数据 a,b

完整代码

#include<stdio.h>
int main()
{
	int n, m, i, a, b, cnt = 0, head = 0, d = 1000020;
	static int p[1000020], num[2020] = { 0 };
	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%d", &p[i]);
		if (num[p[i]] == 0) {
			cnt++;
		}/*出现新的种类,计数器加一*/
		num[p[i]]++;
		while (num[p[head]] > 1) {
			num[p[head]]--;
			head++;
		}/*头部种类出现两次,头部右移一位*/
		if (cnt == m) {
			if (i - head + 1 < d) {
				d = i - head + 1;
				a = head;
				b = a + d - 1;
			}
		}/*满足条件,更新数据 a,b*/
	}
	printf("%d %d", a + 1, b + 1);
	return 0;
}