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

typedef struct _ANT
{
    int pos;
    int flags;
} ANT;

#define AF_ILL 1
#define AF_OUT 2

// 判断蚂蚁i是否与另一只蚂蚁相遇
// n为蚂蚁总数
// 返回值: 相遇的另一只蚂蚁的序号
// 如果没有相遇的蚂蚁, 返回-1
int meet(ANT *ants, int n, int i)
{
    int j;
    for (j = 0; j < n; j++)
    {
        if (j == i || (ants[j].flags & AF_OUT))
            continue;
        if (abs(ants[j].pos) == abs(ants[i].pos))
            return j;
    }
    return -1;
}

void meetcheck(ANT *ants, int n, int i, int *pIll)
{
    int a = meet(ants, n, i);
    if (a == -1)
        return;

    ants[i].pos--;
    ants[a].pos--;
    ants[i].pos = -ants[i].pos;
    ants[a].pos = -ants[a].pos;

    // 感冒判定
    if ((ants[i].flags & AF_ILL) && !(ants[a].flags & AF_ILL))
    {
        ants[a].flags |= AF_ILL;
        (*pIll)++;
    }
    if ((ants[a].flags & AF_ILL) && !(ants[i].flags & AF_ILL))
    {
        ants[i].flags |= AF_ILL;
        (*pIll)++;
    }
}

// 返回值: out的增加值
int walk(ANT *ants, int n, int i, int *pIll)
{
    if (ants[i].flags & AF_OUT)
        return 0;

    ants[i].pos++;
    meetcheck(ants, n, i, pIll);
    if (ants[i].pos == 0 || abs(ants[i].pos) >= 100)
    {
        ants[i].flags |= AF_OUT;
        return 1;
    }
    return 0;
}

int main()
{
    int n, i;
    int ill = 1;
    int out = 0;
    ANT *ants;
    scanf_s("%d", &n);
    ants = (ANT *)malloc(n * sizeof(ANT));
    for (i = 0; i < n; i++)
    {
        scanf_s("%d", &ants[i].pos);
        if (i == 0)
            ants[i].flags = AF_ILL;
        else
            ants[i].flags = 0;
    }

    while (out < n)
    {
        for (i = 0; i < n; i++)
            out += walk(ants, n, i, &ill);
    }

    printf("%d\n", ill);

    free(ants);
    return 0;
}

部分数据会导致程序死循环无法得出结果。

蚂蚁感冒  03-13 14:59  1.336KB  C  运行超时  50  运行超时  1.601MB  评测详情 


还好得了50分
看来就是部分数据死循环的问题

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

typedef struct _ANT
{
    int pos;
    int flags;
    int refcnt;
} ANT;

#define AF_ILL 1
#define AF_OUT 2

int meet(ANT *ants, int n, int i)
{
    int j;
    if (ants[i].refcnt > 100)
        return -1;
    for (j = 0; j < n; j++)
    {
        if (j == i || (ants[j].flags & AF_OUT) || ants[j].refcnt > 100)
            continue;
        if (abs(ants[j].pos) == abs(ants[i].pos))
            return j;
    }
    return -1;
}

void meetcheck(ANT *ants, int n, int i, int *pIll)
{
    int a = meet(ants, n, i);
    if (a == -1)
        return;

    ants[i].refcnt++;
    ants[a].refcnt++;
    ants[i].pos--;
    ants[a].pos--;
    ants[i].pos = -ants[i].pos;
    ants[a].pos = -ants[a].pos;

    if ((ants[i].flags & AF_ILL) && !(ants[a].flags & AF_ILL))
    {
        ants[a].flags |= AF_ILL;
        (*pIll)++;
    }
    if ((ants[a].flags & AF_ILL) && !(ants[i].flags & AF_ILL))
    {
        ants[i].flags |= AF_ILL;
        (*pIll)++;
    }
}

int walk(ANT *ants, int n, int i, int *pIll)
{
    if (ants[i].flags & AF_OUT)
        return 0;

    ants[i].pos++;
    meetcheck(ants, n, i, pIll);
    if (ants[i].pos == 0 || abs(ants[i].pos) >= 100)
    {
        ants[i].flags |= AF_OUT;
        return 1;
    }
    return 0;
}

int main()
{
    int n, i;
    int ill = 1;
    int out = 0;
    ANT *ants;
    scanf("%d", &n);
    ants = (ANT *)malloc(n * sizeof(ANT));
    for (i = 0; i < n; i++)
    {
        scanf("%d", &ants[i].pos);
        ants[i].refcnt = 0;
        if (i == 0)
            ants[i].flags = AF_ILL;
        else
            ants[i].flags = 0;
    }

    while (out < n)
    {
        for (i = 0; i < n; i++)
            out += walk(ants, n, i, &ill);
    }

    printf("%d\n", ill);

    free(ants);
    return 0;
}

评测结果：错误
得分：50

得了一半的分还是不错了