題目描述
超市正在特價售賣巧克力，正好被貪吃的 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;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/43029.html
標籤：C
上一篇：C語言設計實驗報告（第三次）
下一篇：指標陣列與陣列指標