目录
  1. 1. 题目描述
  2. 2. 思路
算法-KTV问题

题目描述

有n个人去KTV唱歌,每个人都有自己想唱的一些歌曲。已知该KTV的每个房间都只有x个麦克风,同一首歌可以同时多个人一起唱,但是同时唱的人不能超过x个人,同一时刻只能唱一首歌。一共只有y首歌的时间,所有人想唱的歌都唱完或者y首歌唱完了他们就会离开。他们想知道在最优的安排策略下(让每个人尽量唱完自己想唱的歌曲),当他们离开时是否还有人有想唱但没唱的歌曲。
输入:

第一行一个整数T,表示测试的数据组数1<=T<=10;
对于每组测试数据,第一行3歌证书n,x,y,含义见题面,1<=n<=100,1<=x<=100,1<=y<=1000;
接下来n行按行从上到下顺序分别给出了第1到第n个人想唱的歌曲,其中每行开头一个证书a[i]表示第i个人想唱歌的数量,后面a[i]]歌整数,表示歌曲编号1<=a[i]<]10,KTV可选歌曲总数不超过1000,即编号不大于1000。

输出:

对于每组测试数据,离开时有人还有歌没唱完,输出”NO”,否则YES;

样例输入:

1
3 3 3
1 2
1 3
1 4

样例输出

YES

样例输入2:

2
1 1 1
2 1 2
2 2 1
1 1
1 1

样例输出2:

NO
YES

思路

逆向思维,歌曲总数1000,编号分别是1-1000,我们定义歌曲数组a[1001],分别代表1-1000的歌曲需要唱多少次,初始化位0。
遍历循环每个人的所有想唱歌曲,对应的歌曲数组加1。
然后,设总共需要的时间为spendTime=0,进行数组判断,如果为0,跳过,不为0的话,如果刚好整除话筒的个数x,则spendTime加a[i]/x,否则加a[i]/x + 1。
最后进行判断,如果小于等于y,输出yes,否则no。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int loop = scanner.nextInt();
for (int i = 0; i < loop; i++) {
int songs[] = new int[1001];
for (int p = 1; p < songs.length; p++) {
songs[p] = 0;
}
int n = scanner.nextInt();//人
int x = scanner.nextInt();//话筒
int y = scanner.nextInt();//总时间y首
for (int j = 0; j < n; j++) {
int cnt = scanner.nextInt();
for (int k = 0; k < cnt; k++) {
songs[scanner.nextInt()]++;
}
}
int spendTime = 0;
for (int j = 1; j < songs.length; j++) {
if (songs[j] == 0) continue;
else {
if (songs[j] % x == 0){
spendTime =spendTime + songs[j] / x ;
}
else {
spendTime =spendTime + (songs[j] / x + 1);
}
}
}
if (spendTime<=y){
System.out.println("YES");
}else {
System.out.println("NO");
}
}

}
}
文章作者: 李浩
文章链接: https://leehoward.cn/2019/10/17/算法-KTV问题/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 leehoward
打赏
  • 微信
  • 支付宝

评论