首页 > 试题广场 >

手串

[编程题]手串

热度指数：2285 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

作为一个手串艺人，有金主向你订购了一条包含n个杂色串珠的手串——每个串珠要么无色，要么涂了若干种颜色。为了使手串的色彩看起来不那么单调，金主要求，手串上的任意一种颜色（不包含无色），在任意连续的m个串珠里至多出现一次（注意这里手串是一个环形）。手串上的颜色一共有c种。现在按顺时针序告诉你n个串珠的手串上，每个串珠用所包含的颜色分别有哪些。请你判断该手串上有多少种颜色不符合要求。即询问有多少种颜色在任意连续m个串珠中出现了至少两次。

输入描述:

第一行输入n，m，c三个数，用空格隔开。(1 <= n <= 10000, 1 <= m <= 1000, 1 <= c <= 50) 接下来n行每行的第一个数num_i(0 <= num_i <= c)表示第i颗珠子有多少种颜色。接下来依次读入num_i个数字，每个数字x表示第i颗柱子上包含第x种颜色(1 <= x <= c)

输出描述:

一个非负整数，表示该手链上有多少种颜色不符需求。

示例1

输入

输出

说明

第一种颜色出现在第1颗串珠，与规则无冲突。
第二种颜色分别出现在第 1，3，4颗串珠，第3颗与第4颗串珠相邻，所以不合要求。
第三种颜色分别出现在第1，3，5颗串珠，第5颗串珠的下一个是第1颗，所以不合要求。
总计有2种颜色的分布是有问题的。 
这里第2颗串珠是透明的。

算法知识视频讲解

Java

盛夏的清凉

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    int findDuplicate() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();   //n个珠子
        int m = sc.nextInt();   //每m个珠子不得重复颜色
        int c = sc.nextInt();   //共c种颜色
        int k = 0;              //第k颗串珠
        int wrongNum = 0;       //分布有问题的颜色数量
        List<List<Integer>> colorList = new ArrayList<>(c);
        for (int i = 0; i < c; i++) {
            colorList.add(new ArrayList<>());
        }
        //每个串珠分别存进颜色数组
        for (int i = 0; i < n; i++) {
            k++;
            sc.nextLine();
            int colorNum = sc.nextInt();
            for (int j = 0; j < colorNum; j++) {
                colorList.get(sc.nextInt() - 1).add(k);
            }

        }
        //判断每个颜色是否有问题
        for (int i = 0; i < c; i++) {
            List<Integer> thisList = colorList.get(i);
            for (int j = 0; j < thisList.size(); j++) {
                //如果连续两个之间的间隔小于m，则错误颜色数目+1.且该颜色判断完毕break
                if (j < thisList.size() - 1 && thisList.get(j + 1) - thisList.get(j) < m) {
                    wrongNum++;
                    break;
                }
                //判断最后一个和第一个之间的间隔
                if (j == thisList.size() - 1 && (thisList.get(j) + thisList.get(0)) % n < m) {
                    wrongNum++;
                }
            }
        }
        sc.close();
        return wrongNum;
    }

    public static void main(String[] args) {
        int wrongNum = new Main().findDuplicate();
        System.out.println(wrongNum);
    }
}

发表于 2020-04-25 22:42:24 回复(0)