我要招人

去企业版

首页 > 试题广场 >

小美的彩带

[编程题]小美的彩带

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

小美的彩带是由一条长度为 $n$ 的彩带一直无限循环得到的，彩带的每一个位置都有一个颜色，用 $a_i$ 表示。因此当 $i>n$ 时， $a_i=a_{i-n}$ 。

小美每次会从左往右或从右往左剪一段长度为 $x$ 的彩带，她想知道她每次剪下来的彩带有多少种颜色。

输入描述:

第一行输入两个整数  代表彩带长度、剪彩带次数。
第二行输入  个整数  代表彩带每一个位置的颜色。
此后  行，每行输入一个字符  和一个整数  代表裁剪方向和裁剪长度，其中 '' 说明从左往右剪， '' 说明从右往左剪 。

输出描述:

对于每一次裁剪彩带，在一行上输出一个整数代表颜色数量。

示例1

输入

6 4
1 1 4 5 1 4
L 2
L 3
R 12
R 1

输出

说明

第一次剪彩带，剪下来的是  ，有  这  种颜色；
第二次剪彩带，剪下来的是  ，有  这  种颜色；
第三次剪彩带，剪下来的是  ，有  这  种颜色。
第四次剪彩带，剪下来的是  ，有  这一种颜色。

算法知识视频讲解

Java

丗湜

package com.e;  import java.util.*;  /**  * 10 10  * 4 5 3 10 4 7 10 5 4 8  * L 8  * R 4  * L 3  * L 4  * L 1  * L 3  * R 4  * R 3  * L 10  * L 10  * 这个案例没通过  *  *  * 1   5  1  5  * 2   4  2  4  * 3   3  3  2  * 4   4  4  4  * 5   1  5  1  * 6   3  6  3  * 7   3  7  4  * 8   3  8  3  * 9   6  9  6  * 10  6  10 6  */ public class 减彩带 { public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);  int n = scanner.nextInt();  int q = scanner.nextInt();  int[] colors = new int[n];  Set<Integer> set=new HashSet<>();  for (int i = 0; i < n; i++) {
            colors[i] = scanner.nextInt();  set.add( colors[i]);  } // 初始化裁剪区间  int start = 0;  int end = -1;   int leftIndex=0;  int beforLeftIndex=0;   int rightIndex=0;  int beforeRightIndex=0;  int ColorCount[]=new int[q-1];  for(int j=0;j<q;j++){
            String derect=scanner.next();  int cutCount=scanner.nextInt();  if(derect.equals("L")){ if(cutCount>=colors.length){
                    ColorCount[j]= set.size();  beforLeftIndex=leftIndex;  leftIndex=(beforLeftIndex+cutCount)%colors.length;  } if(cutCount<colors.length){
                    beforLeftIndex=leftIndex;  leftIndex=(beforLeftIndex+cutCount)%colors.length;  ColorCount[j]=getColorSizeLeft(beforLeftIndex,leftIndex,colors);  }
            } //从右到左的下标取值时，要从颜色数组的反向取  if(derect.equals("R")){ if(cutCount>=colors.length){
                    ColorCount[j]= set.size();  beforeRightIndex=beforeRightIndex;  rightIndex=(rightIndex+cutCount)%colors.length;  } if(cutCount<colors.length){
                    beforLeftIndex=leftIndex;  leftIndex=(leftIndex+cutCount)%colors.length;  ColorCount[j]=getColorSizeRight(beforLeftIndex,leftIndex,colors);  }
            }
        } for (int i = 0; i < ColorCount.length; i++) {
            System.out.print(ColorCount[i]+" ");  }

    } public static int getColorSizeLeft(int startIndex,int endIndex,int[] colors){
        Set<Integer> set=new HashSet<>();  if(endIndex>startIndex){ for(int i=startIndex;i<endIndex;i++){
              set.add(colors[i]);  }
      }else{ for(int i=startIndex;i<colors.length;i++){
              set.add(colors[i]);  } for(int i=0;i<endIndex;i++){
              set.add(colors[i]);  }
      } return set.size();  } public static int getColorSizeRight(int startIndex,int endIndex,int[] colors){
        Set<Integer> set=new HashSet<>();  if(endIndex>startIndex){ for(int i=startIndex;i<endIndex;i++){
                set.add(colors[(colors.length-1)-i]);  }
        }else{ for(int i=startIndex;i<colors.length;i++){
                set.add(colors[colors.length-1-i]);  } for(int i=0;i<endIndex;i++){
                set.add(colors.length-1-i);  }
        } return set.size();  }
}

发表于 2025-02-23 11:13:36 回复(1)

Java

云深尽处

Java貌似做不了？？？运行超时，C++可以

发表于 2024-12-16 13:50:54 回复(0)

Java

法学小鑫

首先，我没有做出来这道题目，但是想要谈一下自己的理解。

1.第一种思路，暴力直接遍历整个数组，那么时间复杂度和空间复杂度大致是O（n）O（n）。

于是乎给定k组查询，那么时间复杂度应该是O（nk），下意识感觉不太行。

2.假定第一种思路是失败的，那么有没有第二种思路可以优化呢？如果单次查询指定区间的颜色数量如果是O（1）或者O（log n）那么k次查询复杂度是O（k）或者O（k*logn）。似乎这样的答案才是符合要求的。

思路就戛然而止了...

发表于 2024-09-08 15:00:50 回复(0)

提交观点

问题信息

难度：

3条回答 119收藏 5442浏览

小美的彩带

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题