题解 | #合并表记录#

#include <stdio.h>

/*int main() {
    int hash[11111112]={};
    int n;
    scanf("%d",&n);
    while(n--){
        int index,val;
        scanf("%d %d",&index,&val);
        hash[index]+=val;
    }
    for(int i=0;i<11111112;i++){
        if(hash[i]!=0){
            printf("%d %d\n",i,hash[i]);
        }
    }

    return 0;
}*/
//上述代码导致内存超限，也就是说直接哈希会出问题
int main(){
    int n;
    scanf("%d\n",&n);
    int record[500][2]={};//用来接收输入的值，因为不能保证
    //输入的值是按照index递增的方式进行的，所以没办法直接在线处理
    for(int i=0;i<n;i++){
        scanf("%d %d\n",&record[i][0],&record[i][1]);
    }
    //接下来对record中的值进行排序，从小到大按照index排序；
    for(int i=0;i<n;i++){
        int min = record[i][0];
        int minIndex = i;
        int j;
        for(j=i+1;j<n;j++){
            if(record[j][0]<min){
                min = record[j][0];
                minIndex = j;
            }
        }
        int tmp = record[i][0];
        int tmp1 = record[i][1];
        record[i][0]=record[minIndex][0];
        record[i][1]=record[minIndex][1];
        record[minIndex][0]=tmp;
        record[minIndex][1]=tmp1;
    }
    //下面对已经排好序的数据进行合并和输出，直接处理
    int tmpIndex = record[0][0];
    int tmpValue = record[0][1];
    for(int i=1;i<n;i++){
        if(record[i][0]==tmpIndex){
            tmpValue+=record[i][1];
        }
        else{
            printf("%d %d\n",tmpIndex,tmpValue);
            tmpIndex = record[i][0];
            tmpValue = record[i][1];
        }
    }
    printf("%d %d\n",tmpIndex,tmpValue);
    return 0;
}

本题最开始的解题思路是直接hash，发现超过了内存限制，于是采用第二种解法

存储index-value对，根据index值按照非递减序列排序，再采用在线处理的方式进行合并输出，总体时间复杂度为排序的时间复杂度，此处为O（n^2），采用其他更高效的排序算法可以达到O（nlogn）的程度。