好吃的巧克力题解
程序员文章站
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; }
上一篇: 北航OO(2020)第一单元博客作业
下一篇: java I/O流