描述

题目描述：

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

输入描述：

第一行一个整数T，表示测试的数据组数1≤T≤10；

对于每组测试数据，第一行三个整数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”。（不包括引号）。

思路

……

实现

#include<stdio.h>
#include<stdlib.h>

void insertSeq(int arr[], int size, int key)
{
  int index = 0;

  for(int i = 0; i < size; i++) {
    if(arr[i] >= key){
      index = i;
      break;
    } else{
      index++;
    }
  }
  for(int i = size; i > index; i--){
    arr[i] = arr[i - 1];
  }
  arr[index] = key;
  //printf("\narr[%d]:%d:%d\n", index, key, size);

  return ;
}

int checkComplete(int arr[], int size, int x_pers, int y_songs)
{
  int i, flag = 0;
  int key_id;
  int need_songs = 0, repeat = 0;

  i = 0;
  while (i < size) {
    need_songs++;
    key_id = arr[i];
    repeat = 0;
    while(arr[i] == key_id) {
      repeat++;
      i++;
      if (repeat >= x_pers)
        break;
    }
    //printf("while %d:%d:%d\n", i, need_songs, repeat);
  }
  if (need_songs <= y_songs)
    flag = 1;

  //printf("res:size=%d,%d:%d:flag=%d", size, need_songs, y_songs,flag);
  return flag;
}

int main()
{
  int T, n, x, y;
  int tempId, flag;
  int size = 0;
  int *arr_p, *arr_yp;

  scanf("%d", &T);
  for (int k = 0; k < T; k++) {
    size = 0;
    scanf("%d %d %d", &n, &x, &y);
    arr_p = (int *)malloc(n * sizeof(int));
    arr_yp = (int *)malloc(x * y * sizeof(int));
    for (int i = 0; i < n; i++) {
      scanf("%d", &arr_p[i]);
      for (int j = 0; j < arr_p[i]; j++) {
        scanf("%d", &tempId);
        insertSeq(arr_yp, size, tempId);
        size++;
      }
    }

    flag = checkComplete(arr_yp, size, x, y);
    printf("%s\n", (flag == 1)? "YES":"NO");
    free(arr_p);
    free(arr_yp);
  }

  return 0;
}