题解 | #合并表记录#

#include <stdio.h>

struct node {
    int index;
    int value;
    struct node* next;
};
int main() {
    int n;
    struct node* header = (struct node*) calloc(sizeof(struct node), 1);

    int index, value;
    scanf("%d", &n);

    for (int i = 0 ; i < n; i++) {
        scanf("%d %d", &index, &value);
        if (header->next == NULL) {
            struct node* indexNode = (struct node*) calloc(sizeof(struct node), 1);
            header->next = indexNode;
            indexNode->index = index;
            indexNode->value = value;
        } else {
            struct node* p = header;
            while (p != NULL) {
                if (p->next == NULL) {
                    struct node* new = (struct node*) calloc(sizeof(struct node), 1);
                    new->next = p->next;
                    p->next = new;
                    new->index = index;
                    new->value = value;
                    break;
                } else if (p->next->index >= index) {
                    if (p->next->index == index) {
                        p->next->value += value;
                    } else {
                        struct node* new = (struct node*) calloc(sizeof(struct node), 1);
                        new->next = p->next;
                        p->next = new;
                        new->index = index;
                        new->value = value;
                    }
                    break;
                } else   {
                    p = p->next;
                }

            }
        }
    }

    struct node* p = header;
    while(p->next != NULL){
        printf("%d %d\n", p->next->index, p->next->value);
        p = p->next;
    }

    return 0;
}

我以为这样实现复杂度会小一点，还是低估了，不过这样内存占用应该是最小的了