PTA 实验五 JAVA语言 7

7-2 超市贴花

分数 20

全屏浏览

切换布局

作者 翁恺

单位 浙江大学

某超市有一种促销手段，购买金额超过一定阈值就随机给一个贴花。贴花有不同种类的，种类以编号表示，编号是一个1到100之间的数字。当收集到连续编号的三张贴花时，就可以换一个小礼物。

小明经常去某超市购物，积攒了不少贴花，你帮他看看，能换多少小礼物。

首先是一个正整数N(1<N<100)，表示小明手上的贴花的数量。
然后是N个正整数Pi​(1⩽Pi​⩽1000，每个数字表示一张贴花的编号。

输出一个数字，表示小明可以换的小礼物的数量。如果不能换小礼物，就输出0。

6

3 2 4 6 6 4

1

2 3 4是一个组合，之后剩下的4 6 6不是连续的编号

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

import java.util.Scanner;

import java.util.HashMap;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int[] stickers = new int[n];

for (int i = 0; i < n; i++) {

stickers[i] = scanner.nextInt();

}

int giftCount = countGifts(stickers);

System.out.println(giftCount);

}

public static int countGifts(int[] stickers) {

HashMap<Integer, Integer> stickerCount = new HashMap<>();

int giftCount = 0;

for (int sticker : stickers) {

stickerCount.put(sticker, stickerCount.getOrDefault(sticker, 0) + 1);

if (stickerCount.containsKey(sticker - 2) && stickerCount.containsKey(sticker - 1) &&

stickerCount.containsKey(sticker)) {

int minCount = Math.min(stickerCount.get(sticker - 2),

Math.min(stickerCount.get(sticker - 1), stickerCount.get(sticker)));

giftCount += minCount;

stickerCount.put(sticker - 2, stickerCount.get(sticker - 2) - minCount);

stickerCount.put(sticker - 1, stickerCount.get(sticker - 1) - minCount);

stickerCount.put(sticker, stickerCount.get(sticker) - minCount);

}

}

return giftCount;

}

}