PAT Basic 1069. 微博转发抽奖

1. 题目描述：

小明 PAT 考了满分，高兴之余决定发起微博转发抽奖活动，从转发的网友中按顺序每隔 N 个人就发出一个红包。请你编写程序帮助他确定中奖名单。

2. 输入格式：

输入第一行给出三个正整数 M（≤ 1000）、N 和 S，分别是转发的总量、小明决定的中奖间隔、以及第一位中奖者的序号（编号从 1 开始）。随后 M 行，顺序给出转发微博的网友的昵称（不超过 20 个字符、不包含空格回车的非空字符串）。

注意：可能有人转发多次，但不能中奖多次。所以如果处于当前中奖位置的网友已经中过奖，则跳过他顺次取下一位。

3. 输出格式：

按照输入的顺序输出中奖名单，每个昵称占一行。如果没有人中奖，则输出 Keep going...。

4. 输入样例：

9 3 2
Imgonnawin!
PickMe
PickMe
LookHere
Imgonnawin!
TryAgainAgain
TryAgainAgain
Imgonnawin!
TryAgainAgain

2 3 5
Imgonnawin!
PickMe

5. 输出样例：

PickMe
Imgonnawin!
TryAgainAgain

Keep going...

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

关键在于维护两个二维字符数组，二维字符数组pRepo用于存储所有转发的用户昵称，pUser用于记录已中奖的用户。从第一位中奖序号开始以给定间隔遍历pRepo，在输出中奖信息前判断当前用户是否中过奖，是则检查下一元素，否则输出中奖信息并将当前用户加入到pUser中。

关键还是在于二维字符数组的malloc定义，第一次提交时testpoint4报Segmentation Fault就是因为malloc语句分配的大小写错了。。。只能说涉及到内存管理的语句要格外小心。另外就是如果想把这种数组指针作为参数传递的话，形参需要先定义为void *类型（参考子函数alreadyIn()），这个点需要注意下。

My Code:

#include <stdio.h>
#include <stdlib.h> // malloc header
#include <string.h> // strcmp header, strcpy header

#define MAX_LEN 21

int alreadyIn(void *des, int userCount, char *current);

// first submit testpoint4 Segmentation Fault, for malloc size have wrong...
int main(void)
{
    int repostCount = 0, interval = 0, first = 0;
    int i=0; // iterator
    int userCount = 0;
    //int j=0; // iterator
    
    scanf("%d%d%d", &repostCount, &interval, &first);
    // here must be sizeof(char[MAX_LEN])
    char (*pRepo)[MAX_LEN] = (char (*)[MAX_LEN])malloc(sizeof(char[MAX_LEN]) * repostCount);
    char (*pUser)[MAX_LEN] = (char (*)[MAX_LEN])malloc(sizeof(char[MAX_LEN]) * repostCount);
    for(i=0; i<repostCount; ++i)
    {
        scanf("%s", pRepo[i]);
    }
    
    for(i=first-1; i<repostCount; i+=interval)
    {
        while(alreadyIn(pUser, userCount, pRepo[i])) // already win a prize
        {
            ++i;
        }
        
        //char *strcpy(char *dest, const char *src)
        strcpy(pUser[userCount++], pRepo[i]);
        printf("%s\n", pRepo[i]);
    }
    
    if(!userCount)
    {
        printf("Keep going...\n");
    }
    
    free(pRepo);
    free(pUser);
    return 0;
}

int alreadyIn(void *des, int userCount, char *current)
{
    char (*pUser)[MAX_LEN] = (char(*)[MAX_LEN]) des;
    int i=0;
    
    for(i=0; i<userCount; ++i)
    {
        if(!strcmp(pUser[i], current))
        {
            return 1;
        }
    }
    
    return 0;
}