题目描述:
让我们来模拟一个消息队列的运作;有一个发布者和若干消费者;发布者会在给定的时刻向消息队列发送消息;
*若此时消息队列有消费者订阅;这个消息会被发送到订阅的消费者中优先级最高(输入中消费者按优先级升序排列)的一个;
*若此时没有订阅的消费者,该消息被消息队列丢弃。
消费者则会在给定的时刻订阅消息队列或取消订阅。
*当消息发送和订阅发生在同一时刻时,先处理订阅操作,即同一时刻订阅的消费者成为消息发送的候选。
*当消息发送和取消订阅发生在同一时刻时,先处理取消订阅操作,即消息不会被发送到同一时刻取消订阅的消费者。
输入描述:
输入为两行。
第一行为2N个正整数,代表发布者发送的N个消息的时刻和内容(为方便解折,消息内容也用正整数表示)。第一个数字是第一个消息的发送时刻,第二个数字是第一个消息的内容,以此类推。用例保证发送时刻不会重复,但注意消息并没有按照发送时刻排列。
第二行为2M个正整数,代表M个消费者订阅和取消订阅的时刻。第一个数字是第一个消费者订阅的时刻,第二个数字是第一个消费者取消订阅的时刻,以此类推。用例保证每个消费者的取消订阅时刻大于订阅时刻,消费者按优先级升序排列。
两行的数字都由空格分隔。N不超过100,M不超过10,每行的长度不超过1000字符。
输出描述:
输出为M行,依次为M个消费者收到的消息内容,消息内容按收到的顺序排列,且由空格分隔;
若某个消费者没有收到任何消息,则对应的行输出-1.
测试用例1:
输入:
2 22 1 11 4 44 5 55 3 33
1 7 2 3
输出:
11 33 44 55
22
说明:消息11在1时刻到达,此时只有第一个消费者订阅,消息发送给它;
消息22在2时刻到达,此时两个消费者都订阅了,消息发送给优先级最高的第二个消费者;
消息33在时刻3到达,此时只有第一个消费者订阅,消息发送给它;
余下的消息按规则也是发送给第一个消费者。
测试用例2:
输入:
5 64 11 64 9 97
9 11 4 9
输出:
97
64
说明:
消息64在5时刻到达,此时只有第二个消费者订阅,消息发送给它;
消息97在9时刻到达,此时只有第一个消费者订阅(因为第二个消费者刚好在9时刻取消订阅),消息发送给它;
11时刻也到达了一个内容为64的消息,不过因为没有消费者订阅,消息被丢弃。
解题思路:
1、消息按照到达的时刻排序;
2、查询每条消息,按照优先级顺序是否到达(反向遍历),如果在消费者订阅,并未取消订阅存入数组;
3、判断消息达到时刻是否满足消费者要求,满足收集打印。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N_MAX 100
#define M_MAX 10
int analysis(char *str,int (*arr)[2]){
int len = strlen(str);
char *temp_str = (char *)malloc(sizeof(char)*5);
int cnt = 0,num = 0,arr_cnt = 0;
temp_str = strtok(str," ");
while(temp_str != NULL){
num = atoi(temp_str);
if(cnt % 2 == 0){
arr[arr_cnt][0] = num;
}else{
arr[arr_cnt++][1] = num;
}
cnt++;
temp_str = strtok(NULL," ");
}
free(temp_str);
return arr_cnt;
}
int cmp(const void *a,const void *b){
int *arr1 = *(int **)a;
int *arr2 = *(int **)b;
int wa = arr1[0];
int wb = arr2[0];
return wa - wb;
}
int main(){
// int news[N_MAX][2],news_cnt;
int **news = (int **)malloc(sizeof(int *)*N_MAX);
int news_cnt = 0;
int consumer[M_MAX][2],consumer_cnt;
char news_str[500];
char consumer_str[100];
fgets(news_str,500,stdin);
fgets(consumer_str,100,stdin);
//把消息与消费者订阅消息解析,存储进2维数组
char *temp_str = (char *)malloc(sizeof(char)*5);
int cnt = 0,num = 0;
temp_str = strtok(news_str," ");
while(temp_str != NULL){
num = atoi(temp_str);
if(cnt % 2 == 0){
news[news_cnt] = (int *)malloc(sizeof(int)*2);
news[news_cnt][0] = num;
}else{
news[news_cnt++][1] = num;
}
cnt++;
temp_str = strtok(NULL," ");
}
free(temp_str);
consumer_cnt = analysis(consumer_str,consumer);
//消息按照到达的时刻排序
qsort(news,news_cnt,sizeof(int*),cmp);
//定义存储消费者收到消息内容
int output[consumer_cnt][N_MAX];
//定义消费者收到消息内容的数量
int output_cnt[consumer_cnt];
memset(output_cnt,0x00,sizeof(int)*consumer_cnt);
//遍历每条消息
for(int i = 0;i < news_cnt;i++){
//查询每条消息,按照优先级顺序是否到达(反向遍历),如果在消费者订阅,并未取消订阅存入数组
for(int j = consumer_cnt - 1;j >= 0;j--){
//判断消息达到时刻是否满足消费者要求
if(news[i][0] >= consumer[j][0] && news[i][0] < consumer[j][1]){
//消息存入前面定义消费者的收到消息数组
output[j][output_cnt[j]++] = news[i][1];
break;
}
}
}
//逐个打印消费者储存的消息
for(int i = 0;i < consumer_cnt;i++){
if(output_cnt[i] == 0){
printf("-1\n");
}else{
for(int j = 0;j < output_cnt[i];j++){
printf("%d ",output[i][j]);
}
printf("\n");
}
}
}
Python代码
news = list(map(int,input().split()))
consumers = list(map(int,input().split()))
news_list = []
consumers_list = []
for i in range(0,len(news),2):
news_list.append([news[i],news[i+1]])
for i in range(0,len(consumers),2):
consumers_list.append([consumers[i],consumers[i+1]])
#消息按照到达时刻排序
news_list.sort(key=lambda x: x[0])
#定义消费者收到消息内容的数量
res_list = []
for i in range(len(consumers_list)):
res_list.append([])
#遍历每条消息
for i in range(len(news_list)):
#查询每条消息,按照优先级顺序是否到达(反向遍历),如果在消费者订阅,并未取消订阅存入数组
for j in range(len(consumers_list),0,-1):
#判断消息达到时刻是否满足消费者要求
if consumers_list[j - 1][0] <= news_list[i][0] < consumers_list[j - 1][1]:
res_list[j - 1].append(news_list[i][1])
break
#逐个打印消费者消息
for contents in res_list:
if len(contents) == 0:
print("-1")
else:
print(" ".join(map(str, contents)))